Permutation Generation Graph with Even Cycles

Consider a permutation (p) of the set ([1, n]). The generation graph of (p) is defined as an undirected graph with (n) nodes where for every (1 \leq i \leq n) there is an undirected edge ((i, p_i)) and no other edges exist. Note that a self-loop (i.e. when (p_i = i)) is considered as a cycle as well.


Your task is to count how many permutations (p) of ([1, n]) have a generation graph with an even number of cycles. Recall that the cycle decomposition of the permutation naturally gives the cycles in the generation graph, hence, the problem reduces to counting the number of permutations with an even number of cycles.

Hint: It is well known that for (n \geq 2), the number of permutations with an even number of cycles is (\frac{n!}{2}), and for (n = 1), the answer is (0) since there is only one cycle.

inputFormat

The input consists of a single integer (n) ((1 \leq n \leq 20)).

outputFormat

Output a single integer representing the number of permutations (p) of ([1, n]) whose generation graph has an even number of cycles.

sample

1

0