1 #include <iostream>
2 #include <cstring>
3 #include <string>
4 #include <algorithm>
5 #define mod 10000000;
6 using namespace std;
7 typedef long long ll;
8 int main()
9 {
10 ll x, n;
11 cin >> x >> n;
12 ll ans = 1;
13 while (n > 0)
14 {
15 if (n & 1)//如果二进制最低位为1，则乘上
16 ans = ans * x%mod;
17 x = x * x%mod;//将x平方
18 n >>= 1;//右移1位，相当于/2；
19 }
20 cout << ans;
21 }