Description

这是一道结合了基础数论和线性代数的题目。 已知 n×n 方阵 A 满足 ai,j=ijgcd(i,j),请求出 det(A) 对 m 取模的结果。

Input Format

从文件 all.in 中读入数据。

本题有多组数据。 输入的第一行包含两个正整数 T,m分别表示数据组数和模数。 接下来 T行，每行一个整数 ni，表示你需要对 ni×ni的方阵 A 求出其行列式。

Output Format

输出到文件 all.out 中。 输出 T行，其中第 i 行包括一个正整数，表示 det(A) mod m。

Sample

样例输入

6 1000000007
1
2
3
4
5
6

样例输出

1
4
72
2304
230400
16588800

Hint

对于 10%的数据，ni≤6。 对于 30%的数据，ni≤10。 对于 50%的数据，ni≤500。 对于 80%的数据，ni≤1000000。 对于 100%的数据，1≤ni≤10000000,1≤T≤1000,max{ni}<m≤1000000007。