A tuple of positive integers (a, b, c) is said to be a *bad tuple* if a, b, c are distinct, a divides b, and b divides c. For example, (1, 2, 4) and (7, 21, 42) are bad tuples while (1, 2, 3) and (2, 4, 4) are not.

Chef has the N integers from 1 to N with him. He wants to pick a [subset] of these numbers such that it doesn't contain a *bad tuple*. How many distinct subsets can he pick?

------ Input Format ------ 

- The first and only line of input contains a single integer N, the number of available integers.

------ Output Format ------ 

Output the number of subsets that don't contain any bad tuples in them.

------ Constraints ------ 

$1 ≤ N ≤ 60$

----- Sample Input 1 ------ 
2

----- Sample Output 1 ------ 
4

----- explanation 1 ------ 

----- Sample Input 2 ------ 
4

----- Sample Output 2 ------ 
14

----- explanation 2 ------ 
Test case $1$: There are $4$ subsets in total — $\{\}$, $\{1\}$, $\{2\}$, $\{1, 2\}$. None of these subsets violate the condition.

Test case $2$: There are $16$ subsets in total, out of which $2$ subsets — $\{1, 2, 4\}$ and $\{1, 2, 3, 4\}$ — violate the given condition as they contain the bad tuple $(1, 2, 4)$ in them.

Source: codechef | Difficulty: VERY_HARD
Tags: Mathematics


Solutions:
l = [2, 4, 8, 14, 28, 48, 96, 156, 296, 550, 1100, 1660, 3320, 6364, 13396, 19704, 39408, 63544, 127088, 207872, 411776, 815120, 1630240, 2314112, 4618992, 9182760, 17224024, 29024656, 58049312, 91231552, 182463104, 286283072, 571753408, 1141547840, 2281913792, 3261222752, 6522445504, 13032175200, 26051468992, 39608033920, 79216067840, 129240099424, 258480198848, 446712574400, 819036722624, 1637645500448, 3275291000896, 4535163453120, 9070137911040, 16652651026624, 33302520651072, 57836427144768, 115672854289536, 182818186855936, 365628884681472, 573179362840320, 1146319028540928, 2292538950900096, 4585077901800192, 6413690997549952]
print(l[int(input()) - 1])