34503번 - Sequence Evaluation 서브태스크다국어

문제

Let $K,ドル $P,ドル and $X$ be integers, where $P$ is prime and 0ドル \le K \le \min(P-1, 8)$.

Define a sequence $a$ of rational numbers as follows:

• $a_1 = 1$.
• For all $n \ge 2,ドル $a_n = X \sum_{i=1}^{n-1} \frac{a_i}{n-i}$.

Output $a_{P-K}$ modulo $P$ (note the unusual modulo). Formally, let $a_{P-K} = \frac{x}{y}$ in lowest terms, and output an integer 0ドル \le b < P$ such that $by \equiv x \pmod{P}$. We can show that such a $b$ exists and is unique under the constraints of this problem.

We recommend that C++ users use the following code, from KACTL, to perform modulo operations faster. Note that creating FastMod instances is a relatively slow operation, so avoid repeatedly doing so for the same modulo.

typedef unsigned long long ull;
struct FastMod {
 ull b, m;
 FastMod(ull b) : b(b), m(-1ULL / b) {}
 ull reduce(ull a) {
 ull q = (ull)((__uint128_t(m) * a) >> 64), r = a - q * b;
 return r - (r >= b) * b;
 }
};

입력

Each test contains multiple test cases. The first line of input contains a single integer $T$ $(1 \leq T \leq 200),ドル the number of test cases. The description of each test case follows.

Each test case consists of one line of input with three integers $K,ドル $P,ドル and $X$ ($\mathbf{0 \le K \le \min(P-1, 8)},ドル 3ドル \le P < 2 \cdot 10^7,ドル 1ドル \le X \le 10^9,ドル $P$ is prime).

It is guaranteed that the sum of $P$ over all test cases does not exceed 2ドル \cdot 10^7$.

출력

For each test case, output a line with a single integer: $a_{P-K}$ modulo $P$.

제한

서브태스크

노트

In the first test case, we have $K = 2,ドル $P = 5,ドル $X = 3,ドル and we want to find $a_{P-K} = a_3$.

We may evaluate the initial elements of $a$ as follows:

• $a_1 = 1$.
• $a_2 = Xa_1 = 3$.
• $a_3 = X(a_1/2 + a_2) = 3(7/2) = 21/2$.

Since 2ドル \cdot 3 \equiv 21 \pmod{5},ドル the answer is 3ドル \pmod 5$.