Easy

Execution time limit is 1 second

Runtime memory usage limit is 64 megabytes

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.

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.

Print a single digit - d_N.

Input #1

Answer #1