Product of GCDs

题号：NC223368
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

ZYT loves GCD(greatest common divisor).

One day, LBC gives him multiple number set ${S}$ , and asks him to calculate the product of greatest common divisors of its each non-empty subsets of size ${k}$ .

In other words, for a number set ${T}$ , let's define $f(T)=\gcd(S_{x_1},S_{x_2},\cdots,S_{x_{|T|}}),x_i\in T$ .Now ZYT should calculate $\prod_{T\subseteq U,|T|=k}f(T)$ , where $U=\{1,2,\cdots,|S|\}$ .

Because the answer is very large, we should output the result of the answer modulo ${P}$ .

输入描述:

The input consists of multiple test cases. The first line contains an integer  — the number of test cases.

In each testcase, the first line contains three integers .

The second line contains  integers , representing the   elements of .

输出描述:

For each test case,output one line containing one integer: .

示例1

输入

复制

1
5 2 20040220
2 4 8 12 14

输出

复制

备注:

It is guaranteed that .

It is not guaranteed that the elements in  are distinct.