All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

The Ghost Type
/

Algorithms, Bitmask, Dynamic Programming

Problem
Editorial
Analytics

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

SAMPLE INPUT
4
SAMPLE OUTPUT
8
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

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?