U362268 【MAROI csp七连Day1】A.Sing

有一个 MAR 数列，它的定义是这样的：对于每一个 $f_{i}(i>2)$：$f_i=f_{i-1} \times f_{i-2}$，并且对于每个 $f_i(i>2)$，需要对 $i$ 取模，现在给出 $f_1,f_2$ 的值，需要你求出 $f_n$ 的值。

三个正整数 $f_1,f_2,n$。

这个序列的第 $n$ 项的值。

**【样例解释 \#1】** 这个序列为：$\{1,5,2,2,4\}$，第 $5$ 项是 $4$， **【样例解释 \#2】** 这个序列为：$\{9,10\}$，第 $2$ 项是 $10$， **【样例 \#3】** 见附件中的 `A3.in` 与 `A3.out`。 **【样例 \#4】** 见附件中的 `A4.in` 与 `A4.out`。 **【数据范围】** 对于 $10\%$ 的数据，$1 \le f_1,f_2,n \le 2$， 对于 $20\%$ 的数据，$1 \le f_1,f_2,n \le 10$， 对于 $30\%$ 的数据，$1 \le f_1,f_2,n \le 10^2$， 对于 $50\%$ 的数据，$1 \le f_1,f_2,n \le 10^3$， 对于 $70\%$ 的数据，$1 \le f_1,f_2,n \le 10^5$， 对于 $90\%$ 的数据，$1 \le f_1,f_2,n \le 10^7$， 对于 $100\%$ 的数据，$1 \le f_1,f_2,n \le 10^8$。