背景

本题出处：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$。

输出格式

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

10
1 1 4
5 1 4
1 9 1
9 8 1
0 2 3
2 4 3
2 3 3
3 4 9
7 7 8
0 0 8

1
2
1
9
0
2
0
0
6
0

提示

【样例解释 #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}$。

其中：

• 特殊性质 $\text{A}$：保证 $x,y,n$ 随机生成。