Gengar has got an integer N. Now using his ghostly powers, he can create the permutation from 1 to N of this given number.

Since, he's a special kind of Poke'mon, so he thinks he deserves special permutations. He wants to find the total number of special permutations of length N, consisting of the integers from 1 to N.

A permutation is called special if it satisfies following condition:

If A_p & A_q == A_p, then p < q, where p and q are two distinct indices of permutation and A is the permutation itself. "&" denotes the bitwise and operation.

Help Gengar in finding the number of such permutations.

Input format:
The only line of input will consist of a single integer N denoting the length of the permutation.

Output format:
Output the total number of special permutations of length N.

Constraints:
1 ≤ N ≤ 20

References: