Crypto

Pesho is crypting a permutation of $n$ numbers where each integer from $1$ to $n$ appears exactly once. He is using the following algorithm:

1. Replace each initial number $x$ with the $x$-th prime number.

2. Choose a random positive integer $k$, not greater than $n$.

3. Consider all subsequences with consecutive elements. For each subsequence with at least $k$ elements write down the product of the smallest $k$ numbers.

4. Let $p$ be the number of unique products written in the previous step.

5. The code is "$n$ $k$ $p$".

Let us see how Pesho should crypt the permutation {$4$, $1$, $3$, $2$}:

$1$. The first $4$ prime numbers are $2$, $3$, $5$ and $7$. In the initial permutation he replaces

• $4$ with the fourth prime number which is $7$;

• $1$ with the first prime number which is $2$;

• $3$ with the third prime number which is $5$;

• $2$ with the second prime number which is $3$.

Pesho obtains the new sequence $7$, $2$, $5$, $3$.

$2$. He chooses a random number $k$. Say $k$ = $2$.

$3$. All contiguous subsequences are:{$7$}, {$2$}, {$5$}, {$3$}, {$7$, $2$}, {$2$, $5$}, {$5$, $3$}, {$7$, $2$, $5$}, {$2$, $5$, $3$}, {$7$, $2$, $5$, $3$}

Pesho removes all subsequences with less than $k$ = $2$ elements and for each of the rest he computes the product of the smallest $k$ = $2$ elements

• {$7$, $2$} $2$ * $7$ = $14$

• {$2$, $5$} $2$ * $5$ = $10$

• {$5$, $3$} $3$ * $5$ = $15$

• {$7$, $2$, $5$} $2$ * $5$ = $10$

• {$2$, $5$, $3$} $2$ * $3$ = $6$

• {$7$, $2$, $5$, $3$} $2$ * $3$ = $6$

He writes the numbers {$14$, $10$, $15$, $10$, $6$, $6$}

$4$. There are four unique numbers: {$6$, $10$, $14$, $15$}, thus $p$ = $4$.

$5$. The code is "$4$ $2$ $4$".

Pesho quickly figured out that the algorithm is much better than he expected. He cannot always decrypt the code unambiguously.

Write a program, which given a code calculates the number of possible initial permutations. Find the answer modulo $1000000007$.