Counting Functions

Time limit1sMemory limit32 MB

Summary

Count functions f on {1..N} such that each i returns to itself after exactly A_i iterations, for N up to 16.

Level: Hard8 of 10
Topics: Combinatorics, Graph, Bit manipulation
Solved: No attempts yet

Problem

Minhyuk built a function $f : S \to S$ from the set $S = \{1, 2, \dots, N\}$ to itself. Write $f^k$ for applying $f$ exactly $k$ times in a row. The function Minhyuk built satisfies the following.

$f^{A_1}(1) = 1$
$f^{A_2}(2) = 2$
$\dots$
$f^{A_N}(N) = N$

Minhyuk wants to know how many different functions satisfy this. Given $A_1, A_2, \dots, A_N$ , write a program that counts them. Two functions $g$ and $h$ are different when there is at least one $x$ with $g(x) \neq h(x)$ .

Input

The first line contains the size of the domain, $N$ . ( $3 \le N \le 16$ )

The second line contains the positive integers $A_1, A_2, \dots, A_N$ , separated by spaces. ( $1 \le A_i \le 1{,}000{,}000$ )

Output

Print the number of functions that satisfy the condition on the first line.

Examples2

Example 1
Input
```
4
3 6 9 12
```
Expected output
```
10
```

Example 2

Input

16
720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720 720720

Expected output

20922789888000