欧拉定理（称费马-欧拉定理或欧拉 函数定理）
欧拉定理表明，若n,a为正整数，且n,a互素(即gcd(a,n)=1)，则
这个定理可以用来简化幂的模运算。比如计算7222的个位数，实际是求7222被10除的余数。7和10互素，且fai(10)=4。由欧拉定理知
所以
则对于(ab^c)%1000000007
根据欧拉定理, a的fai(1000000007)和1同余，那么把bc分解成(n*fai(m)+r)的形式，(ab^c) 就变成了 A(n*fai(m)+r)，那么就变成了 A(n*fai(m)*Ar，又A(n*fai(m)和1同余，那么只要求Ar即可。
已知fai(m)是同1到与m互质的数的个数，故应为100000006。