There is a positive integer sequence $a_1,a_2,...,a_n$ with some unknown positions, denoted by 0. Little Q will replace each 0 by a random integer within the range $[1,m]$ equiprobably. After that, he will calculate the value of this sequence using the following formula :
\begin{eqnarray*}
\prod_{i=1}^{n-3} v[\gcd(a_i,a_{i+1},a_{i+2},a_{i+3})]
\end{eqnarray*}
Little Q is wondering what is the expected value of this sequence. Please write a program to calculate the expected value.

The first line of the input contains an integer $T(1\leq T\leq10)$, denoting the number of test cases.
In each test case, there are $2$ integers $n,m(4\leq n\leq 100,1\leq m\leq 100)$ in the first line, denoting the length of the sequence and the bound of each number.
In the second line, there are $n$ integers $a_1,a_2,...,a_n(0\leq a_i\leq m)$, denoting the sequence.
In the third line, there are $m$ integers $v_1,v_2,...v_m(1\leq v_i\leq 10^9)$, denoting the array $v$.

For each test case, print a single line containing an integer, denoting the expected value. If the answer is $\frac{A}{B}$, please print $C(0\leq C<10^9+7)$ where $A\equiv C\times B\pmod{10^9+7}$.