题目描述

在这道题中，我们定义一个新的运算符号 $\oplus$ 并将其称为新取模运算。

当计算 $x \oplus y$ 时，如果 $x$ 不是 $y$ 的倍数，则得到 $x$ 除以 $y$ 的余数; 否则令 $x$ 不断除以 $y$ 直到 $x$ 不再是 $y$ 的倍数，假设它为 $x'$，然后得到 $x'$ 除以 $y$ 的余数。例如，$4\oplus 5=4$，$20\oplus 5=4$，$100\oplus 5=4$。

给定一个质数 $p$，接下来会有多组询问，对于每次询问会给出一个整数 $n$，你需要计算出 $n!\oplus p$ 的值。其中 $n!$ 是 $n$ 的阶乘，即所有小于等于 $n$ 的正整数的乘积。

输入格式

第一行包含两个整数 $T\ (1\le T\le 10^5)$ 和 $p\ (2\le p\le 10^6)$，分别表示询问的次数和给定的质数。

接下来 $T$ 行，每行包含一个整数 $n\ (1\le n\le 10^{18})$，含义如题目所述。

输出格式

对于每次询问，输出一行包含一个整数，即 $n!\oplus p$ 的值。

3 7
11
45
14

4
1
2

2 10007
1919
810

3152
3679