C. Two Cats
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After your death, you're sent to a mysterious room. There are two cats guarding two doors, one leading to heaven of AC problems and the other leading to hell NO. One cat likes all divisors of an integer a, a being the product of n integers v1, v2, ..., vn. The other cat likes all integers with exactly b divisors. You were asked to count the number of integers that satisfy both cats. If you count correctly, you may go to the heaven of AC problems, full of balloons, otherwise you're sent to hell NO.

As the answer can be quite large, print the remainder of this number modulo 109 + 7.

Input

The first line of the input contains two integers b (1 ≤ b ≤ 103) and n (1 ≤ n ≤ 103).

The following line contains n space separated integers v1, v2, ..., vn (2 ≤ vi ≤ 1012) whose product is a.

Output

Output a single integer - the number of integers that satisfy both cats modulo 109 + 7.

Examples
Input
2 3
19 5 2
Output
3
Input
3 2
366 169
Output
1