intaddM(int a, int b, int mod = MOD){ return (a += b) >= mod ? a - mod : a; } intsubM(int a, int b, int mod = MOD){ return (a -= b) < 0 ? a + mod : a; } intmulM(int a, int b, int mod = MOD){ return (i64)a * b % mod; }
i64 mulM(i64 a, i64 b, i64 mod){ return (i128)a * b % mod; } i64 qpow(i64 a, i64 b, i64 mod){ i64 ans = 1 % mod; for (a %= mod; b; b >>= 1, a = mulM(a, a, mod)) if (b & 1) ans = mulM(ans, a, mod); return ans; }
/* Fufffh */ #include<bits/stdc++.h> usingnamespace std; using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t; using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;
i64 mulM(i64 a, i64 b, i64 mod){ return (i128)a * b % mod; } i64 qpow(i64 a, i64 b, i64 mod){ i64 ans = 1 % mod; for (a %= mod; b; b >>= 1, a = mulM(a, a, mod)) if (b & 1) ans = mulM(ans, a, mod); return ans; }
int32_tmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 a, b, p; cin >> a >> b >> p; cout << a << '^' << b << " mod " << p << '=' << qpow(a, b, p) << '\n'; return0; }
/* Fufffh */ #include<bits/stdc++.h> usingnamespace std; using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t; using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y){ if (!b) { x = 1; y = 0; return a; } i64 g = exgcd(b, a % b, y, x); y -= a / b * x; return g; }
int32_tmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 a, b, c, x, y; cin >> a >> b >> c; c = -c; i64 g = exgcd(abs(a), abs(b), x, y); if (c % g) { cout << -1 << '\n'; return0; } x *= c / g; y *= c / g; if (a < 0) x = -x; if (b < 0) y = -y; cout << x << ' ' << y << '\n'; return0; }
/* Fufffh */ #include<bits/stdc++.h> usingnamespace std; using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t; using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y){ if (!b) { x = 1; y = 0; return a; } i64 g = exgcd(b, a % b, y, x); y -= a / b * x; return g; }
int32_tmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 x, y, m, n, l; cin >> x >> y >> m >> n >> l; i64 a = m - n, b = y - x, p, q; i64 d = exgcd(abs(a), l, p, q); if (b % d) { cout << "Impossible\n"; return0; } if (a < 0) p = -p; i128 ans = (i128)p * (b / d) % (l / d); if (ans < 0) ans += l / d; cout << (i64)ans << '\n'; return0; }
/* Fufffh */ #include<bits/stdc++.h> usingnamespace std; using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t; using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y){ if (!b) { x = 1; y = 0; return a; } i64 g = exgcd(b, a % b, y, x); y -= a / b * x; return g; }
int32_tmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 a, b, x, y; cin >> a >> b; exgcd(a, b, x, y); x %= b; if (x < 0) x += b; cout << x << '\n'; return0; }
/* Fufffh */ #include<bits/stdc++.h> usingnamespace std; using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t; using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t; constint MOD = 1e9 + 7;
intsubM(int a, int b, int mod = MOD){ return (a -= b) < 0 ? a + mod : a; } intmulM(int a, int b, int mod = MOD){ return (i64)a * b % mod; } intqpow(int a, i64 b, int mod = MOD){ int ans = 1; for (; b; b >>= 1, a = mulM(a, a, mod)) if (b & 1) ans = mulM(ans, a, mod); return ans; } intcomb(i64 n, int m){ int a = 1, b = 1; for (int i = 1; i <= m; i++) { a = mulM(a, (n - i + 1) % MOD); b = mulM(b, i); } returnmulM(a, qpow(b, MOD - 2)); }
int32_tmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 n; int a, b; cin >> n >> a >> b; int ans = subM(subM(subM(qpow(2, n), 1), comb(n, a)), comb(n, b)); cout << ans << '\n'; return0; }
/* Fufffh */ #include<bits/stdc++.h> usingnamespace std; using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t; using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;
i64 mulM(i64 a, i64 b, i64 mod){ return (i128)a * b % mod; } i64 phi(i64 n){ i64 ans = n; for (i64 p = 2; p * p <= n; p++) if (n % p == 0) { ans = ans / p * (p - 1); while (n % p == 0) n /= p; } if (n > 1) ans = ans / n * (n - 1); return ans; } i64 qpow(i64 a, i64 b, i64 mod){ i64 ans = 1 % mod; for (a %= mod; b; b >>= 1, a = mulM(a, a, mod)) if (b & 1) ans = mulM(ans, a, mod); return ans; } pair<i64, bool> parse(const string &s, i64 mod){ i64 rem = 0, val = 0; bool large = false; for (char c : s) { int x = c - '0'; rem = (rem * 10 + x) % mod; if (!large) { val = val * 10 + x; if (val >= mod) large = true; } } return {rem, large}; }
int32_tmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 a, mod; string b; cin >> a >> mod >> b; i64 ph = phi(mod); auto [e, large] = parse(b, ph); if (large) e += ph; cout << qpow(a, e, mod) << '\n'; return0; }
/* Fufffh */ #include<bits/stdc++.h> usingnamespace std; using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t; using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;
i64 addM(i64 a, i64 b, i64 mod){ i128 x = (i128)a + b; return x >= mod ? x - mod : x; } i64 mulM(i64 a, i64 b, i64 mod){ return (i128)a * b % mod; } pair<i64, i64> calc(i64 a, i64 n, i64 mod){ if (!n) return {1 % mod, 0}; auto [p, s] = calc(a, n >> 1, mod); i64 p2 = mulM(p, p, mod), s2 = mulM(s, addM(p, 1 % mod, mod), mod); if (!(n & 1)) return {p2, s2}; return {mulM(p2, a, mod), addM(s2, p2, mod)}; }
int32_tmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 a, x, mod; cin >> a >> x >> mod; cout << calc(a % mod, x, mod).second << '\n'; return0; }