e-olymp
Problems

Sequence (2)

Sequence (2)

Each member of the sequence of decimal digitsd1, d2, d3, ..., starting from the fourth, the last digit is the sum of the previous three. On the setd1, d2, d3find the N-th term of the sequence.

Input

In the first row are the numbersd1, d2, d3, separated by spaces, in the second - the numberN.

1N1015.

Output

Print a single digit - dN.

Time limit 1 second
Memory limit 64 MiB
Input example
Sample 1
1 4 8
4

Sample 2
5 5 5
1000000000000000
Output example
Sample 1
3

Sample 2
5