题目描述
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 10^9+7.
Constraints:
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^8
SAMPLE INPUT
6
2 3 5 6 7 8
SAMPLE OUTPUT
2
Explanation
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}
输入格式
见题面
输出格式
见题面