Description
This is a Sierpinski Carpet.
The construction of a Sierpinski Carpet is stated as follows. Initially, you are given a white square.
-
Divide the square into nine subsquares in a 3-by-3 grid.
-
Color the center subsquare with black.
-
For the rest eight subsquare, repeat step 1
For example,
Initially (after zero iteration), there is 0 black square in the Sierpinski Carpet.
After one iteration, there is 1 black square in the Sierpinski Carpet.
After two iterations, there are 9 black squares in the Sierpinski Carpet.
After three iterations, there are 73 black squares in the Sierpinski Carpet
Given an integer k, please output number of black squares after k iterations.
Maybe Useless Hint
-
It is suggested to solve this problem using recursion. (Well ... there is mathematic solution, but hope you practice how to design recursion function)
-
Be careful with overflow. Suggest to calculate with long long int.
Input
Input contain a single integer k.
Since there will be overflow issue if k is too big, so in this problem 0 <= k < 10.
Output
Output the number of black squares after the k-th iteration.
Note that there is a newline character after the output.