Micro is working on a product in his internship. Name of the product is "Product". It takes an array A having N integers as input and count the number of good subsequences of that array. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. A good subsequence is one in which the product of all the numbers in subsequence is divisible by all numbers from 1 to 9. Help Micro build this thing.
Input:
First line of input consists of an integer denoting N.
Second line consists of N space separated integers denoting the array A.
Output:
Print the number of good subsequences in the array A. Since the answer can be large print it modulo 109+7.
Constraints:
1≤N≤105
1≤A[i]≤108
Following are the subsequences, products of whose elements is divisible by all numbers from 1 to 9:
{2,3,5,6,7,8}
{3,5,6,7,8}
