Descripción

Es el cumpleaños de Karel, y su amigo Ahmed decide regalarle un número muy grande. Desafortunadamente, Karel le tiene fobia a valores mayores a ~10^{18}~, por lo que Ahmed le entrega un arreglo ~A~ y un arreglo ~B~, y le dice que su número es el resultado de:

$$\displaystyle \prod ^N _{i=1} {A_i^{B_i}} $$

En otras palabras, el número se puede expresar como el producto de cada elemento del arreglo ~A~ elevado al elemento del arreglo ~B~ con mismo índice.

Lamentablemente, le entregaron a Ahmed un tercer arreglo ~C~ y le contaron en último momento que a Karel le encantan los números que son ~C_i~ -potencia para todo ~1 \le i \le M~, o sea, que se debe cumplir que ~X=k^{C_i}~, siendo ~X~ el número que cumple las condiciones de Karel y ~k~ un valor que puede variar con tal de cumplir la igualdad para cada ~C_i~.

Tarea

Ahmed quiere modificar un poco su regalo para que cumpla con las preferencias de su amigo y necesita tu ayuda para ello. Diga el menor entero positivo por el cual Ahmed tiene que multiplicar su regalo para que satisfaga las condiciones antes mencionadas.

Puede que este número sea muy grande, así que estamos interesados en su módulo ~10^9 + 7~.

Cabe destacar que debido al terrible miedo de Karel a valores grandes, Ahmed se asegura que cualquier operación aritmética con propiedad conmutativa que se efectúe sobre todos los elementos del arreglo ~C~ va a dar como resultado un número que no excede ~5\cdot {10^{17}}~, exceptuando la multiplicación.

Se define la propiedad conmutativa como aquella que al operar dos elementos no depende del orden en que se tomen. Un ejemplo de esto sería la suma o multiplicación de dos valores.

Entrada

La primera línea contiene un entero ~T~ (~1 \le T \le 1000~), el números de casos de prueba. Cada uno de estos contiene dos enteros ~N~ y ~M~ separados por un espacio, el tamaño de los arreglos ~A~ y ~B~, y el tamaño del arreglo ~C~, respectivamente.

La segunda línea continene ~N~ enteros separados por espacios, el i-ésimo es ~A_i~ ~(1 \le A_i \le 10^6)~.

La tercera línea continene ~N~ enteros separados por espacios, el i-ésimo es ~B_i~ ~(1 \le B_i \le 10^9)~.

La cuarta línea continene ~M~ enteros separados por espacios, el i-ésimo es ~C_i~ ~(1 \le C_i \le 10^6)~.

Salida

Imprima un solo entero, el valor por el cual se debe multiplicar el regalo de Ahmed para satisfacer las condiciones de los números que le gustan a Karel módulo ~10^9+7~.

Subtareas

• Subtarea ~1~ (~10~ puntos): ~M = 1~ y ~C_1 = 2~.
• Subtarea ~2~ (~15~ puntos): ~A_i = A_{i-1}~ para todo ~2 \le i \le N~.
• Subtarea ~3~ (~25~ puntos): ~1 \le N~, ~M \le 500~.
• Subtarea ~4~ (~50~ puntos): Sin restricciones adicionales.

Ejemplo de Entrada y Salida

Entrada

3
8 1
2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9
2
1 3
248918
545795
364583 619091 67301
3 2
6 6 6
1 2 3
5 7

Salida

105
257399592
321781213