#include using namespace std; #define gc getchar_unlocked #define fo(i,n) for(int i=0;in;k 0) { if (exp & 1) result = ((ll)result * base) % mod; base = ((ll)base * base) % mod; exp >>= 1; } return result; }