405294: GYM101875 C Two Cats

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 v₁, v₂, ..., v_n. 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 10⁹ + 7.

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

The following line contains n space separated integers v₁, v₂, ..., v_n (2 ≤ v_i ≤ 10¹²) whose product is a.

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

2 3
19 5 2

3

3 2
366 169

1