べき乗 10^9乗なんてまともにやると大変なので m^2n = m^n * m^nという関係を使ってlog nのオーダにしてやる 余りを求めろとなってるのは a * b % q == (a % q) * (b % q)だから毎回余りをとってやればよかろう 1000000007で割るというのは32ビットで収まる…