Description

现在 lhm 手中有一个无穷长的衔尾数列 $a$，它满足：

• 对于数列中的每一个 $a_i(i>2)$，它总为 $a_{i-2} \times a_{i-1}$ 的个位数。

ducati 将给 lhm 衔尾数列的前两位 $a_1=n,a_2=m$ 与位置 $k$，它的任务是算出 $a_k$。

由于 lhm 太菜了并不会这道题，但他仍然想成为人 win，所以他只好请聪明的你来帮他完成这个问题。

Input Format

第一行三个整数 $n,m,k$。

Output Format

一行一个整数，表示数列中位置 $k$ 的数字。

1 6 10

6

7 2 7

2

Hint

【样例解释 $1$】

数列 $1$ 至 $10$ 位依次为：$1,6,6,6,6,6,6,6,6,\color{red}{6}$。所以答案为 $6$。

【样例解释 $2$】

数列 $1$ 至 $7$ 位依次为：$7,2,4,8,2,6,\color{red}{2}$。所以答案为 $2$。

【数据范围】

本题采用捆绑测试。

• Subtask 1（30pts）：$1 \leq k \leq 10^6$。
• Subtask 2（70pts）：无特殊限制。

对于 $100\%$ 的数据，$0 \leq n,m \leq 9$，$1 \leq k \leq 10^{12}$。