二乗 Bash(Beta)編（paizaランク B 相当）

繰り返し二乗法は、x^n の形の累乗計算を高速におこなう手法です。
具体的には、n の 2 進数表記を用いて、x^{2^i} のうち必要なものだけを掛け合わせることで高速に計算します。
たとえば、x^{11} = x^{1 + 2 + 8} = x^{2^0 + 2^1 + 2^3} = x^{2^0} × x^{2^1} × x^{2^3} となります。

では、実際に x^{2^i} を計算してみましょう。
x と k が与えられるので、x^{2^0}, x^{2^1}, x^{2^2}, ..., x^{2^{k-1}} を計算してください。
ただし、答えは非常に大きくなる可能性があるので、10000000 = 10^7 で割ったあまりを出力してください。

ヒント: x^{2^i} = x{2^{i-1} × 2} = (x^{2^{i-1}})^2 です。