Gengar has got an integer A. Now using his ghostly powers, he can create the permutation from 1 to A 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 A.
A permutation is called special if it satisfies following condition:
If Px & Py == Px, then x < y, where x and y are two distinct indices of permutation and P is the permutation itself. “&” denotes the bitwise and operation.
Help Gengar in finding the number of such permutations.
First and only argument of input conatins a single integer A
Ouput a string denoting the answer.
1 <= A <= 20
Example Input 1: A = 3 Example Output 1: 2 Explanation 1: Special Permutation are: [1, 2, 3] and [2, 1, 3] Example Input 2: A = 4 Example Output 2: 8
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.