Each member of the sequence of decimal digits \textbf{d_1}, \textbf{d_2}, \textbf{d_3}, ..., starting from the fourth, the last digit is the sum of the previous three. On the set \textbf{d_1}, \textbf{d_2}, \textbf{d_3} find the \textbf{N}-th term of the sequence. \InputFile In the first row are the numbers \textbf{d_1}, \textbf{d_2}, \textbf{d_3}, separated by spaces, in the second - the number \textbf{N}. \textbf{1} ≤ \textbf{N} ≤ \textbf{10^15}. \OutputFile Print a single digit - \textbf{d_N}.