P16345 阿瓦的数列

本题出处：https://www.luogu.com.cn/contest/314899 阿瓦想要创造一个数列！

阿瓦创造了一个数列 $a$， 这个数列的第一项为 $x$，第二项为 $y$，在第二项之后的每一项都有： - $a_i = a_{i-1} \times a_{i-2} \bmod i$。 现在阿瓦给你了三个数 $x,y,n$，你需要求出 $a_n$ 的值。 由于阿瓦怕你蒙混过关，因此本题多测。

第一行一个正整数 $T$，表示数据组数。 对于每组测试数据，每行输入三个正整数 $x,y,n$。

对于每组测试数据，输出一个非负整数表示你的答案。

**【样例解释 #1】** 这里仅解释前三组询问。 对于第一组询问，$a_1=1$，$a_2=1$，$a_3=1$，$a_4=1$。 对于第二组询问，$a_1=5$，$a_2=1$，$a_3=2$，$a_4=2$。 对于第三组询问，$a_1=1$。 [](请记住这个样例，它也许可以帮助你度过难关。) **【数据范围】** 对于所有测试数据保证：$1 \le T \le 10^5$，$1 \le n \le 10^{18}$，$0 \le x,y \le 10^{18}$。 | 测试点编号 | $T \le$ | $n \le$ | $x,y \le$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1,2$ | $10^5$ | $10$ | $10^{9}$ | 无 | $3$ | $10^5$ | $10$ | $10^{18}$ | 无 | | $4$ | $10^5$ | $10^{18}$ | $1$ | 无 | | $5$ | $10^5$ | $10^2$ | $10^{18}$ | 无 | | $6$ | $10^5$ | $10^{18}$ | $10$ | 无 | | $7$ | $10^5$ | $10^{18}$ | $10^3$ | 无 | | $8$ | $10^5$ | $10^{18}$ | $10^9$ | $\text{A}$ | | $9$ | $10^5$ | $10^{18}$ | $10^9$ | 无 | | $10$ | $10^5$ | $10^{18}$ | $10^{18}$ | 无 | 其中： - 特殊性质 $\text{A}$：保证 $x,y,n$ 随机生成。