Given a number N which is of the form (2 ^ x - 1) or (2 ^ x - 2)

Find the number of permutations of [1 , n] such that when inserted into a binary search tree from leftmost element of the permutation to rightmost element of the permutation , the tree obtained is Balanced ( it has a height of ceil(log(n + 1)) )

Constraints

1 <= N <= 10 ^ 6

N is always of the form (2 ^ x) - 1 or (2 ^ x) - 2

Sample

Input

1

Output

1

Input

2

Output

2

Input

3

Output

2

Input

6

Output

80

Input

7

Output

80

Explaination

For n = 3

the permutations which yield balanced binary search tree are

[2 , 1 , 3] and [2 , 3 , 1]