安徽科技工程大学程序设计在线考试系统Ver3.0

诚信考试,杜绝作弊!

问题 G: 又见斐波那契数列

内存限制:512 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

描述

斐波那契数列大家应该很熟悉了吧。下面给大家引入一种新的斐波那契数列:M斐波那契数列。 M斐波那契数列F[n]是一种整数数列,它的定义如下:

F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )

现在给出a, b, n,聪明的你能求出F[n]的值吗?

输入格式

输入包含多组测试数据;
每组数据占一行,包含3个整数a, b, n( 0 <= a, b, n <= 10^9 )

输出格式

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

输入样例 复制

0 1 0 
6 10 2

输出样例 复制

0 
60