3x+1
"3x+1" problem is well known among mathematicians, and even any schoolboy can understand it. Suppose, that a natural number is given. If it is even, divide it by 2. If it is odd, multiply it by 3 and add 1. Then do the same with the result. And so on...
For example, if 5 is given, we get a chain:
5 (*3+1) 16 (/2) 8 (/2) 4 (/2) 2 (/2) 1 (*3+1) 4
and the chain has a loop (4-2-1).
So, if we take any natural number as a head, at last we get 1. This is proven for all natural numbers not exceeding 10^19.
You are to count how many natural numbers, being used as a head for the chain, will give the chain of length N numbers exactly. The trailing 1 is not counted.
Chain 5-16-8-4-2-1, mentioned above, has length of 5.
Also, the 1-4-2-1 loop must not be taken in count. For example, consider 1-4-2-1 an incorrect chain of length 3.
Input
The only line contains natural number N (1 ≤ N ≤ 62).
Output
The only line should contain one natural number - the answer to the problem.