Good Permutations

Given an integer n, count the number of good permutations of the set {1, 2, ..., n} that satisfy the following condition: when computing the cumulative bitwise AND of the permutation from the first element up to the i-th element (for each 1 ≤ i ≤ n), the resulting sequence is non-decreasing.

In other words, if the permutation is represented as p[1], p[2], ..., p[n], and if we define A_i = p[1] & p[2] & ... & p[i] (where '&' is the bitwise AND operation), then the sequence A₁, A₂, ..., A_n must satisfy A₁ ≤ A₂ ≤ ... ≤ A_n.

You are required to output the number of such good permutations modulo \(10^9+7\).

Note: It can be proven that when n=1 there is exactly one good permutation, when n=2 there are exactly two good permutations, and for all n \ge 3 there exists no good permutation.

inputFormat

The input consists of a single integer n (in a single line), which represents the number of elements in the permutation.

outputFormat

Output a single integer representing the number of good permutations modulo \(10^9+7\).

1

1