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.
In the first row are the numbersd1, d2, d3, separated by spaces, in the second - the numberN.
1 ≤ N ≤ 1015.
Print a single digit - dN.
1 4 8 4