Guards

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.

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$)

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