問題
Nx を 1,000,000,007(=109+7) で割ったあまりを求めよ．
入力
N x
1 行に整数 N, x が半角空白区切りで与えられる．
制約
- 2 ≦ N ≦ 109
- 0 ≦ x ≦ 1013
x が 32bit 整数の範囲に収まらないことがあるので注意すること．
採点用データのうち、配点の 1 点分については以下の制約も追加で満たす．
- x ≦ 1,000
出力
1 行に、 Nx を 1,000,000,007(=109+7) で割ったあまり で出力する．
入出力例
入力例1
2 3
出力例1
8
23 = 2 × 2 × 2 = 8 である．
入力例2
3 0
出力例2
1
30 = 1 である．
入力例3
114 514
出力例3
554023386
入力例4
2 10000000000000
出力例4
836339738
x が 32bit 整数の範囲に収まらないことがある．