Akabeko 20

Akabeko 20 is a group that performs at a dedicated theater in the Izua region. Each member of Akabeko 20 is supposed to participate in a performance every certain number of days.

Today's performance was attended by all the members. As a producer, you are asked by the members to tell the combination of the members for the upcoming performance. You decide to count the number of combinations of members participating in the performance.

Given the number of members of Akabeko 20 and the number of cycles that each member participates in the performance, write a program to count how many combinations of members to participate. Assume that the group will continue to exist forever with the same members. Note that if no one participates, it is not included in the combinations.

Input

The input is given in the following form.

$N$
$p_1$ $p_2$ ... $p_N$

In the first line, the number of members of Akabeko 20 $N$ ($1 \leq N\leq 20$) is given. In the following line, the period $p_i$ ($1 \leq p_i \leq 40$) that each member participates in the performance is given.

Output

Output the number of combinations of members participating in the performance on one line.

Sample Input and Output

Sample Input 1

3
3 5 2

Sample Output 1

7

Sample Input 2

3
2 3 6

Sample Output 2

3

There are three types of performances: one where only members with a cycle of 2 days participate, one where only members with a cycle of 3 days participate, and one where members with cycles of 2, 3, and 6 days participate.

---