Крипто

Пешо шифрує перестановку з $n$ чисел, де кожне число від $1$ до $n$ зустрічається рівно один раз. Він використовує такий алгоритм:

1. Замінити всі числа в перестановці, де число $x$ замінюється на $x$-е просте число.

2. Вибрати випадкове додатне $k$, що не перевищує $n$.

3. Розглянути всі відрізки, що складаються з підряд ідучих елементів отриманої послідовності, які містять хоча б $k$ елементів. Для кожного з них записати добуток $k$ мінімальних чисел.

4. Нехай $p$ дорівнює кількості різних добутків, отриманих на попередньому кроці.

5. Шифром перестановки буде трійка "$n$ $k$ $p$".

Наприклад, розглянемо, як Пешо зашифрує перестановку {$4$, $1$, $3$, $2$}:

$1$. Перші $4$ простих числа це $2$, $3$, $5$ і $7$. Тому він замінює в перестановці

• $4$ на четверте просте число, тобто $7$;

• $1$ на перше просте число, тобто $2$;

• $3$ на третє просте число, тобто $5$;

• $2$ на друге просте число, тобто $3$.

Пешо отримує послідовність $7$, $2$, $5$, $3$.

$2$. Тепер він вибирає випадкове число $k$. Нехай $k$ = $2$.

$3$. Всі відрізки отриманої послідовності:{$7$}, {$2$}, {$5$}, {$3$}, {$7$, $2$}, {$2$, $5$}, {$5$, $3$}, {$7$, $2$, $5$}, {$2$, $5$, $3$}, {$7$, $2$, $5$, $3$}

З них він залишає тільки ті, які містять хоча б $k$ = $2$ елементи, і для кожного з них обчислює добуток двох мінімальних елементів:

• {$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$

Отримуються наступні добутки {$14$, $10$, $15$, $10$, $6$, $6$}

$4$. Всього в наборі чотири різних добутки: {$6$, $10$, $14$, $15$}, таким чином $p$ = $4$.

$5$. Шифр початкової перестановки "$4$ $2$ $4$".

Пешо швидко зрозумів, що алгоритм шифрує послідовності краще, ніж він очікував. Він хотів, щоб код був взаємно-однозначним, але виявилося, що не завжди можна розшифрувати отриманий шифр.

Напишіть програму, яка за заданим шифром обчислює кількість різних можливих початково заданих перестановок. Виведіть залишок від ділення відповіді на $1000000007$.