# A Trivial Pursuit

It’s time for the Trivia Trot, a competition where
anything—and everything—can be asked! Twilight is absolutely
ready to wreck the competition and win it for the three-peat;
she’s studied *Ancient Legends*, *Wonderbolt History*, and *Spells
So Old, Not Even Star Swirl the Bearded Remembers
Them*...

Here’s the first question:

How many sequences $x_1, x_2, \dots , x_ P$ of $P$ positive integers are there satisfying $\gcd (x_1, x_2, \dots , x_ P) = G_1 \times G_2 \times \dots \times G_ N$ and $\mathrm{lcm}(x_1, x_2, \dots , x_ P) = L_1 \times L_2 \times \dots \times L_ M$?

Crap.

## Input

The first line of input contains three integers, $P$ ($1 \leq P \leq 10^{18}$), $N$ and $M$ ($1 \leq N, M \leq 400$), as described in the question.

The second line of input contains $N$ integers $G_1, G_2, \dots , G_ N$ ($1 \leq G_ i \leq 10^{18}$), as described in the question.

The third line of input contains $M$ integers $L_1, L_2, \dots , L_ M$ ($1 \leq L_ i \leq 10^{18}$), as described in the question.

## Output

Output the a single integer on a line by itself, the answer to the question.

Since this number can be quite large, you should output only the remainder after dividing this number by $10^9+7$.

Sample Input 1 | Sample Output 1 |
---|---|

3 1 2 3 17 18 |
216 |

Sample Input 2 | Sample Output 2 |
---|---|

77 10 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 |