Sequence (2)

Each member of the sequence of decimal digits d_1, d_2, d_3, ..., starting from the fourth, the last digit is the sum of the previous three. On the set d_1, d_2, d_3 find the N-th term of the sequence.

Input

In the first row are the numbers d_1, d_2, d_3, separated by spaces, in the second - the number N.

1 ≤ N ≤ 10^15.

Output

Print a single digit - d_N.

Examples