Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito está estudiando matemática y se ha topado con un ejercicio un sencillo pero que le cuesta trabajo solucionar. El problema consiste en dada una secuencia que se define como: $f(1) = 1$, $f(2)=1$ y $f(n) = (a*f (n-1)+b*f (n-2)) \text{ MOD } 7$. Se quiere calcular el valor de $f(n)$ dado los valores de $a$, $b$ y $n$.

Input

La entrada consiste en múltiples casos de prueba. Cada caso de prueba consiste en una línea que contiene tres enteros $a$, $b$ y $n$ separados por un espacio $(1 \leq a, b \leq 1000, 1 \leq n \leq 10^8)$. El fin de la entrada son tres ceros que no debe de ser procesados.

Output

Por cada caso de prueba se debe de imprimir el valor de $f(n)$ en una sola línea.

Sample test(s)