Problems

# Sequence (2)

# Sequence (2)

Each member of the sequence of decimal digits**d _{1}**,

**d**,

_{2}**d**, ..., starting from the fourth, the last digit is the sum of the previous three. On the set

_{3}**d**,

_{1}**d**,

_{2}**d**find the

_{3}**N**-th term of the sequence.

**Input**

In the first row are the numbers**d _{1}**,

**d**,

_{2}**d**, separated by spaces, in the second - the number

_{3}**N**.

**1** ≤ **N** ≤ **10 ^{15}**.

**Output**

Print a single digit - **d _{N}**.

Input example #1

1 4 8 4

Output example #1

3