C++ Library for Competitive Programming
/*
* @title 数学/繰り返し二乗法
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B
*/
#include <iostream>
#include "emthrm/math/mod_pow.hpp"
int main() {
int m, n;
std::cin >> m >> n;
std::cout << emthrm::mod_pow(m, n, 1000000007) << '\n';
return 0;
}
#line 1 "test/math/mod_pow.test.cpp"
/*
* @title 数学/繰り返し二乗法
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B
*/
#include <iostream>
#line 1 "include/emthrm/math/mod_pow.hpp"
namespace emthrm {
long long mod_pow(long long x, long long n, const int m) {
if ((x %= m) < 0) x += m;
long long res = 1;
for (; n > 0; n >>= 1) {
if (n & 1) res = (res * x) % m;
x = (x * x) % m;
}
return res;
}
} // namespace emthrm
#line 10 "test/math/mod_pow.test.cpp"
int main() {
int m, n;
std::cin >> m >> n;
std::cout << emthrm::mod_pow(m, n, 1000000007) << '\n';
return 0;
}