Description

$WZ$认为自己是世界上最聪明的人（虽然只有他自己这么认为），他最近看斐波那契数列非常不爽，怎么会有这么$2$的数列呢$？？ WZ$认为这太小儿科了，于是乎，$WZ$自己发明了一种数列，他称之为$WZ$数列。这种数列是这样定义的。 $A[0]=a;A[1]=b;$ 然后..... $A[n]=A[n-1]*A[n-2],$

Format

Input

输入包含多组测试数据； 每组数据占一行，包含$3$个整数$a, b, n（ 0 \le a, b, n \le 10^9 ）$

Output

对每组测试数据请输出一个整数$F[n]$，由于$A[n]$可能很大，你只需输出$A[n]$对$1000000007$取模后的值即可，每组数据输出一行。

Samples

0 1 0
6 10 2

0
60

Hints

快速XX算法不解释