eolymp
bolt
Try our new interface for solving problems
Problems

Sequence (2)

Sequence (2)

Time limit 1 second
Memory limit 64 MiB

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 data

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

1N10^15.

Output data

Print a single digit - d_N.

Examples

Input example #1
1 4 8
4
Output example #1
3