410573: GYM104053 G Game

Once upon a time, there were two saints named St. Alice and St. Bob.

Being saints were quite boring, so they decided to play a game. The game was about divisibility.

There were two sets of integers, called $$$A$$$ and $$$B$$$. And there were two integers $$$\alpha, \beta$$$. In the beginning, $$$\alpha = \beta = 1$$$.

Then, they take turns. First of all, Alice takes a turn, then Alice goes first, then Bob, then Alice, then Bob, then Alice, and so on.

In Alice's turn, she must choose a number $$$x$$$ from $$$A$$$, and change $$$\alpha$$$ to $$$\alpha \times x$$$.

In Bob's turn, he must choose a number $$$x$$$ from $$$B$$$, and change $$$\beta$$$ to $$$\beta \times x$$$.

If at some time $$$\alpha \mid \beta$$$ (which means there exists an integer $$$k$$$ such that $$$k \times \alpha = \beta$$$), Bob wins. Alice cannot win, she only wanted to play the game forever.

The saints were smart, so both players made optimal moves (to win or to not lose).

After some experiments, Alice found the game too easy, so she wanted to delete a subset of $$$A$$$ while keeping herself unbeatable. Call a subset of $$$A$$$ valid, if and only if deleting it does not affect Alice's unbeatable position.

Saints live long, and they kept playing. Alice asks you to find the number of valid subsets of $$$A$$$, could you do it?

The first line contains two integers $$$|A|, |B| (1 \leq |A|, |B| \leq 500)$$$ — numbers of elements of $$$A$$$, $$$B$$$, respectively.

The second line cantains $$$|A|$$$ integers $$$a_i$$$ ($$$2 \leq a_i \leq 500, a_i < a_{i+1}$$$) — the elements of $$$A$$$.

The third line cantains $$$|B|$$$ integers $$$b_i$$$ ($$$2 \leq b_i \leq 500, b_i < b_{i+1}$$$) — the elements of $$$B$$$.

Output a single integer — the number of valid subsets of $$$A$$$, modulo $$$10^9+7$$$.

Bob may win even if Alice deletes nothing, which means the saints are making fun of you, but print $$$0$$$ anyway.

2 3
2 6
6 7 8

2

6 13
6 7 12 18 21 29
8 11 12 13 15 16 20 21 23 24 27 28 30

56

In the first example, $$$\{2\}, \{\}$$$ are the only two valid subsets.