众志成城

题目介绍

中华民族是向上的民族，无论遇到什么样的困难，始终是一方有难、八方支援，无论是$2008$年突降巴蜀大地的大地震，还是去年那场突如其来的疫情，中国人民万众一心、众志成城，克服了一个又一个困难，也进一步让我们意识到了团结起来的重要性。

现在我们可以直观感受一下团结的力量，现在有$a,b,c$三个正整数，他们个人的力量可能是微小的，但是团结起来的力量却很大。你现在可以计算$a^{b^{c}}$的值来进行直观感受，因为团结的力量实在是太大了，因此请输出该数字对$100000007$（是一个质数）取模的结果。

输入格式

多组输入，每行三个正整数$a,b,c$

输入样例

7 4 9
8 9 1
2 6 7
9 1 2
11 1 9
77 8 7

输出样例

95820093
34217721
19401972
9
11
6308007

数据范围

$a,b,c$均是int范围内的正整数

HINT

$a^{bc}$和$a^{b^{c}}$可不一样哦

了解一下费马小定理，当$p$为一个质数时，$a^{p-1}\equiv1$ $(mod$ $p)$

如果TLE请使用更好的求幂方法

AUTHOR：ZJD