You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

众所周知，ducati 是人 win。

现在 lhm 也想成为人 win，于是 ducati 扔给了 lhm 下面这道题，并且 ducati 承诺在 lhm 完成此题后教他如何成为人 win。

题目描述

现在 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，所以他只好请聪明的你来帮他完成这个问题。

输入格式

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

输出格式

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

1 6 10

6

7 2 7

2

提示

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