Guards

Time limit2sMemory limit32 MB

Summary

Count the subsets of at least two applicants with pairwise coprime favorite numbers, modulo 1,000,000,007.

Level: Hard8 of 10
Topics: Dynamic programming, Number theory, Combinatorics
Solved: No attempts yet

Problem

Sangsu bought a huge house yesterday. He advertised for guards to watch it, n people applied, and he numbered the applicants 1 to n.

Applicant i has a favorite number $a_i$ , which is a positive integer. When applicants i and j stand guard together and the greatest common divisor of $a_i$ and $a_j$ is 2 or more, the two feel close, talk all night, and fail to watch the house.

Sangsu hires at least 2 applicants, and he wants every pair among the hired applicants to have favorite numbers whose greatest common divisor is 1. Count how many ways he can hire. Two ways are different when the sets of hired numbers are different. Two applicants with the same favorite number are different people, but they cannot be hired together, because their greatest common divisor equals that number and is at least 2.

Input

The first line has the number of applicants n. ( $2 \le n \le 2222$ )

The second line has $a_1, a_2, \dots, a_n$ in order, separated by spaces. ( $1 \le a_i \le 2222$ )

Output

Print the number of ways to hire, taken modulo 1,000,000,007( $=10^9+7$ ).

Examples5

Example 1
Input
```
4
1 2 3 4
```
Expected output
```
7
```
Example 2
Input
```
5
10 12 14 16 18
```
Expected output
```
0
```

Example 3

Input

44
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

Expected output

Example 4
Input
```
5
3 21 7 45 15
```
Expected output
```
3
```
Example 5
Input
```
3
3 2 3
```
Expected output
```
2
```