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].