C - Al treilea Cox

Cerință

Se dă $N$. Câte permutări de ordin $N$ (a mulțimii $\{1, 2, ..., N\}$) există astfel încat $cmmdc(A_i+1,i+1) > 1$ pentru orice $1 \le i \le N$?

Date de intrare

Un singur număr, $N$.

Date de ieșire

Numărul de permutări care respectă condiția.

Restricții și precizări

• $1 \le N \le 23$;
• Se observă ca răspunsul este relativ mic.

Exemplul 1

stdin

4

stdout

2

Explicație

Permutările ${1, 2, 3, 4}$ și ${3, 2, 1, 4}$.

Exemplul 2

stdin

19

stdout

318695040