繰り返し二乗法 PHP編（paizaランク A 相当）

では、実際に繰り返し二乗法を使ってみましょう。

繰り返し二乗法は、次のようなアルゴリズムです。
ここでは、x^n を計算することを考えます。
・ result = 1 とする。
・ i = 1 から k まで、以下の処理を繰り返す。(k は最大のビット数とします。)
1. n の下から i 番目のビットが 1 であるならば、result <- result・x とする。
2. x <- x・x とする。

整数 x と整数 n が与えられるので、x^n を高速に計算してください。
ただし、答えは非常に大きくなる可能性があるため、10000000 = 10^7 で割ったあまりを出力してください。