micro-and-product

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\}

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions: