C. Square Free GCD Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ positive integers $$$a_1,$$$ $$$a_2,$$$ ... $$$,a_n$$$. You are also given $$$m$$$ distinct primes $$$p_1,$$$ $$$p_2,$$$ ... $$$,p_m$$$.

It is guaranteed that every $$$a_i$$$ can be expressed as

$$$a_i = \displaystyle \prod_{j=1}^{m} p_j^{e_{i,j}}, \quad e_{i,j} \geq 0.$$$

That is$$$,$$$ all prime factors of all numbers are among these $$$m$$$ primes.

For any non-empty subset $$$S \subseteq \{1, 2, ..., n\},$$$ let gcd($$$S$$$) = gcd($$$a_i \; | \; i \in S$$$). That is, gcd(S) is the greatest common divisor of all elements of the array $$$a$$$ with their index in that subset.

Define a function $$$sf(x)$$$ – the squarefree part of an integer $$$x$$$ as the product of all distinct primes dividing $$$x$$$. For example:

  • $$$sf(12) = 2 \times 3 = 6$$$ – because $$$2$$$ and $$$3$$$ are the distinct primes that divide $$$12$$$
  • $$$sf(18) = 2 \times 3 = 6$$$
  • $$$sf(1) = 1$$$

Your task is to compute, the sum of squarefree parts of gcds over all non-empty subsets of $$$a$$$. Formally, you have to find the following value:

$$$\displaystyle \sum_{\emptyset \neq S \subseteq \{1, 2, ..., n\}}^{} sf(gcd(S))$$$ mod ($$$10^9 + 7$$$)
Input

First line contains $$$2$$$ integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$), ($$$1 \leq m \leq 20$$$).

The second line contains $$$m$$$ space-separated integers $$$p_1,$$$ $$$p_2,$$$ ... $$$,p_m$$$ ($$$1 \leq p_i \leq 200$$$).

The third line contains $$$n$$$ space-separated integers $$$a_1,$$$ $$$a_2,$$$ ... $$$,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

Output

Output one integer, the required sum mod ($$$10^9 + 7$$$)

Examples
Input
4 3
2 3 5
2 6 10 30
Output
82
Input
1 1
2
8
Output
2