long long f(long long a, long long b, long long c) { int ans = 1; while (b > 0) { if (b % 2 == 1) { ans = ans * a % c; } a = a * a % c; b /= 2; } return ans; }