8659: The Alchemist of the Discrete Mathematics

As a great alchemist, Sophie learns Discrete Mathematics very well.

One day, Sophie finds a magic prime number $p$. From her grandma's teaching, if a polynomial F(x) satisfying that $F(x)\equiv 0(\mathrm{mod}p)$ has a solution, then the polynomial is mysterious.

To understand the property of mysterious polynomials, Sophie studies the roots of polynomial.

Given integer n, prime number $p$ and parameter pc∈Fp, the set S⊆Fp is good, if there exist polynomial f(x),g(x)∈Fp[x] satisfying

1. $deg(f)=n$
2. $g(x)\mid f(x)$, i.e., $g(x)$ divides $f(x)$
3. Call T the set of roots of polynomial $(x)g(c\cdot x)$, then S=T∩Fp

Sophie wonders the number of good sets given n,p and c. Since the answer may be too large, you should output the answer modulo 998244353

If you are not familiar with those notations, please refer to the ``Notes section'' in the pdf statement for formal definition.

The first line contains an integer $\ge 1)$, denoting the number of test cases.

For each test case, there is a line containing three integers p,c,n(1≤c<p≤5∗105,0≤n≤106), whose meaning is already given in the previous statement.

It is guaranteed that the sum of p over all test cases won't exceed 10^7.

2
3 2 2
5 4 2

8
23