| 2 | using namespace std; |
| 3 | |
| 4 | long long modpow(long long a, long long b, long long m) { |
| 5 | // �J��Ԃ����@�ip �� a^1, a^2, a^4, a^8, ... �Ƃ������l���Ƃ�j |
| 6 | long long p = a, Answer = 1; |
| 7 | for (int i = 0; i < 30; i++) { |
| 8 | if ((b & (1 << i)) != 0) { Answer *= p; Answer %= m; } |
| 9 | p *= p; p %= m; |
| 10 | } |
| 11 | return Answer; |
| 12 | } |
| 13 | |
| 14 | const long long mod = 1000000007; |
| 15 | long long a, b; |