InterviewBit Academy is now Scaler!
InterviewBit Academy is now Scaler Academy!

The Ghost Type

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.

Input Format:

    First and only argument of input conatins a single integer A

Output Format:

Ouput a string denoting the answer.


1 <= A <= 20

For Example:

Example Input 1:
   A = 3
Example Output 1:
Explanation 1:
    Special Permutation are: [1, 2, 3] and [2, 1, 3]
Example Input 2:
    A = 4
Example Output 2:
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.
Start solving The Ghost Type on Interview Code Editor
Sign Up
to access hints and editorial solutions for The Ghost Type


Click here to start solving coding interview questions