Umay has written \(N\) integers on the board \(A_1\); \(A_2\); : : : ; \(A_N\). Umut looks for a non-empty subset of indices (1; 2; : : : ; \(N\)) such that the sum of the corresponding numbers on the board are divisible by each number \(D\) between 1 and 10 (1 ≤ \(D\) ≤ 10). Your task is to find the number of subsets Umut is looking for. Two subsets are different is there is at least one index present in only one of them. Since the number of subsets can be very large print the result modulo \(10^9\) + 7.

Input

The first line contains integer \(N\).

The next line contains \(N\) integers \(A_1\); \(A_2\); : : : ; \(A_N\) separated with single spaces.

Output

The number of index subsets modulo \(10^9\) + 7.

Constraints

• \(1 ≤ N ≤ 1000\)
• \(1 ≤ A_i ≤ 10^9\)

Samples

Input(stdin)

4
5040 7560 1234 1286

Output(stdout)

7

Notes

In the first sample there are 7 index subsets Umut accepts:

• [1; 2; 3; 4];
• [1; 2];
• [1; 3; 4];
• [1];
• [2; 3; 4];
• [2];
• [3; 4].