题目背景

众所周知，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

输入 #1

1 6 10

输出 #1

6

输入输出样例 #2

输入 #2

7 2 7

输出 #2

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}~。