描述

小C是个数学迷，总是缠着曾经是数学老师的外婆出题考考自己。外婆当然乐意啦，于是就在纸上写下了下面这个算式：

x^y mod 10007 = ？

这下可把小C给难住了，你能帮助他解决这个问题么？

输入描述

输入包括两个整数，分别表示：x、y（1<=x,y<=1e9）。

输出描述

输出包括一个整数，表示算式的答案。

用例输入 1 

2 10

用例输出 1 

1024

利用快速幂的思想。

关键就是：底数翻倍，指数减半，指数是奇数就单独分出一个底数。

#include <iostream>
#define ll long long
using namespace std;
ll fastpow(ll x, ll y, ll mod) {ll res = 1;x = x % mod;//对底数进行预处理while (y > 0) {if (y % 2) {//如果y是奇数，更新答案res = (res * x) % mod;}x = (x * x) % mod;y /= 2;//底数翻倍，指数减半}return res;
}int main() {ll x, y;cin >> x >> y;ll answer = fastpow(x, y, 10007);cout << answer << endl;return 0;
}