Problem C
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...

Figure 1: Illustration by Kyle Coate.

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$.

3 1 2
3
17 18

216

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

0