A sequence of numbers is called "Mingle" if its length is equal or greater than '2' and every consecutive element in that sequence has a GCD greater than '1'. More formally, if we have a sequence 'a1', 'a2', and 'a3', then for this sequence to be called "Mingle", it should follow the given below expressions:

GCD(a1, a2) > 1

GCD(a2, a3) > 1

Here, GCD denotes the greatest common divisor. You are given an array 'A' of 'N' integers indexed from '0' to 'N - 1'. You have to find the number of maximum length subsequences that are "Mingle" sequences.

A subsequence is an array that can be derived from the original array by deleting some of the elements without changing the order of the remaining elements.

Your goal is to find the number of maximum length "Mingle" subsequences. Since the answer may be very large, return it modulo '10^9 + 7'.

Example:

'N'= 3

'A' = [1, 2, 6, 7, 3]

Here, we can get "(2, 6, 3)" as a maximum length "Mingle" subsequence. There is no other "Mingle" subsequence having length equal to '3'. So, the answer for this example will be '1'.

Detailed explanation (Input/output format, Notes, Images)

Input Format: The first line contains a single integer 'N' denoting the number of elements of the array 'A'.

The following line contains 'N' space-separated integers denoting the elements of the array 'A'.

Output Format:

For each test case, return the integer as described above.

Note:

You don't need to print anything. Just implement the given function. Sample Input 1:

2

9

3 4 9 30 2 11 77 7 7

4

1 1 1 1

Sample Output 1:

2

0

Def mingleseq(n,a): Explanation of sample input 1:

For test case 1:

Here, the maximum length "Mingle" subsequences are "3 9 30 2", and "11 77 7 7". So, the answer for this test case will be '2'.

For test case 2:

Here, all the numbers are '1s'. It is impossible to select elements from this array having GCD greater than '1'. So, the answer for this test case will be '0'.