OpenKattis
CS3233 Open Internet Final Team Contest

Start

2020-04-20 00:00 AKDT

CS3233 Open Internet Final Team Contest

End

2020-04-20 05:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -221 days 18:29:26

Time elapsed

5:00:00

Time remaining

0:00:00

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

\includegraphics[width=0.38\textwidth ]{TBOTwibell.png}
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$.

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