1262: [STT2024WCR1+] 快速数论变换

数论变换（$\mathcal{NTT}$）是离散傅里叶变换（$\mathcal{DFT}$）在数论基础上的实现；快速数论变换（$\mathcal{FNTT}$）是快速傅里叶变换（$\mathcal{FFT}$）在数论基础上的实现。实现上运用了离散傅里叶变换、生成子群、原根、离散对数的知识。

$\mathcal{FNTT}$ 解决的是多项式乘法带模数的情况，可以说有些受模数的限制，数也比较大。目前最常见的模数是 $998244353$，其原根是 $3$。



$\mathcal{FNTT}$ 依赖于原根，原根 $g$ 是在某个质数模数 $P$ 下，对于所有 $i \in [1,P-1]$，$g^i$ 在模 $P$ 意义下互不相同。也就是说，有了原根，就可以由它的幂次生成该质数模数最简剩余系中除 $0$ 外的所有数。一个数的原根可能不唯一。在本题中，我们定义 $g^i$ 为由原根 $g$ 生成的第 $i$ 个数。

输入的第一行一个正整数 $T$，表示数据组数。

接下来 $T$ 行，第 $i+1$ 行包含三个整数 $MOD_i, g_i,n_i$，询问由在模 $MOD_i$ 意义下由原根 $g_i$ 生成的第 $n_i$ 个数的值。

对于每组数据输出一行，表示生成数的值。

3
998244353 3 1
998244353 3 998244352
998244353 3 1919810

3
1
6460598