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]