eolymp
bolt
Try our new interface for solving problems

3x+1

Time limit 2 seconds
Memory limit 64 MiB

"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 data

The only line contains natural number N (1N62).

Output data

The only line should contain one natural number - the answer to the problem.

Examples

Input example #1
1
Output example #1
1
Author Второв Алексей
Source Osipovsky Cup - 2013