Description

Now lhm has an infinite cyclic sequence $a$, which satisfies:

• For every $a_i(i>2)$ in the sequence, it is always the units digit of $a_{i-2} \times a_{i-1}$.

ducati will give lhm the first two terms of the cyclic sequence $a_1=n,a_2=m$ and a position $k$. His task is to compute $a_k$.

Because lhm is too weak and cannot solve this problem, but he still wants to become "human win", he has to ask the smart you to help him finish it.

Input Format

The first line contains three integers $n,m,k$.

Output Format

Output one integer in one line, representing the digit at position $k$ in the sequence.

1 6 10

6

7 2 7

2

Hint

[Sample Explanation 1]

The 1st to 10th terms of the sequence are: $1,6,6,6,6,6,6,6,6,\color{red}{6}$. So the answer is $6$.

[Sample Explanation 2]

The 1st to 7th terms of the sequence are: $7,2,4,8,2,6,\color{red}{2}$. So the answer is $2$.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (30 pts): $1 \leq k \leq 10^6$.
• Subtask 2 (70 pts): no special restrictions.

For $100\%$ of the testdata, $0 \leq n,m \leq 9$, $1 \leq k \leq 10^{12}$.

Translated by ChatGPT 5