Chef has his birthday today so he invites many friends to his birthday party. On his birthday Chef 1 answer below »

Chef has his birthday today, so he invites many friends to his birthday party. On his birthday, Chef as always, makes up a game to entertain his friends.
In the game of Chef, he divides his friends into two groups, ‘Thinkers’ and ‘Guessers’. First group, Thinkers, are asked to think of a positive integer. The integer which they choose can be same. The Chef being the Birthday Boy gives a ‘Special number’.

Now the game is that the second group of friends, i.e. Guessers, need to guess the number of non empty subsets of integers whose product yields out the Chef’s ‘Special number’.

Since, there can be a large number of such subsets, Chef asked them to give the value modulo 1,000,000,007.
Help Chef find the winner of the game.

Input

The first line should be number of test cases t.
For the next t times, input will contain the Special Number, S, and the subsequent line should contain an array of positive integers that were thought, separated by a space, Array A.

Output

For every test case, let the number of subsets (non empty) containing integers which has the special number or on multiplication of all of its elements gives that special number,S be N.
You have to print N modulo 1,000,000,007

Constraints

Should contain all the constraints on the input data that you may have. Format it like:1 = t = 1001 = S = 2,000,000,000Size of the Array A will be between 1 and 100Elements of the Array A will be between 1 and 2,000,000,000

ExampleInput: 4 5 1 2 3 4 12 1 2 3 4 5 6 7 8 9 10 11 12 1 1 1 1 2 2 Output: 0 6 7 1

Explanation

Example case 1.
There is no subset possible with 5 occurring in it.

Example case 2.
There are 6 subsets, namely {1,12}, {2,6}, {4,3}, {12}, {1,2,6}, {1,3,4} .

Example case 3.
There are 7 subsets, namely {1}, {1}, {1}, {1,1}, {1,1}, {1,1}, {1,1,1} .

Example case 4.
There is 1 subset possible with 2 occurring in it which is {2}.