The Ghost Type

3.7

47 votes
Algorithms, Approved, Bit Manipulation, Dynamic Programming, Medium, Ready
Problem

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 Ap & Aq == Ap, 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:
enter image description here

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

All the special permutations of length 4 are:
1 2 3 4
1 2 4 3
1 4 2 3
2 1 3 4
2 1 4 3
2 4 1 3
4 1 2 3
4 2 1 3

Editor Image

?