E. Sequence Evaluation
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \lt 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;
	}
};
Input

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 \lt 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$$$.

Output

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

Scoring
  • ($$$25$$$ points): The sum of $$$P$$$ over all test cases does not exceed $$$10^5$$$.
  • ($$$75$$$ points): No additional constraints.
Example
Input
2
2 5 3
8 199999 123456789
Output
3
42180
Note

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$$$.