Given an array of integers **A** of size **N** .

Value of a subset of array **A** is defined as product of all prime numbers in that subset.

If subset does not have any prime number in it, value of such a subset is 1.

If subset have only one prime number in it, value of such a subset is the prime number itself.

Calculate and return Sum of values of all possible subsets of array **A** % (10^9 + 7).

**Constraints**

```
1 <= N <= 10^5
1 <= A[i] < 2^31
max(A[1], A[2] ,..., A[n]) - min(A[1], A[2] ,..., A[n]) <=10^6
```