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.