/*
C++ Quick Pow with Mod & Matrix Quick Pow with Mod Template
By meowjiao
C++ Quick Pow with Mod & Matrix Quick Pow with Mod Template by meowjiao is marked CC0 1.0. To view a copy of this mark, visit https://creativecommons.org/publicdomain/zero/1.0/
Update:
2024.05
2025.07
2025.12
*/
// Quick Pow
long long qpow(long long a, long long b, long long mod) {
a %= mod;
long long ans = 1;
while (b) {
if (b & 1) {
ans = (ans * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
// Matrix Quick Pow
struct Matrix {
int n, m, a[4][4];
Matrix() {
n = m = 0;
memset(a, 0, sizeof(a));
}
Matrix(int x, int y) {
n = x;
m = y;
memset(a, 0, sizeof(a));
}
Matrix(int x) {
n = m = x;
memset(a,0,sizeof(a));
for (int i = 0; i < n; i++) {
a[i][i] = 1;
}
}
Matrix operator+(const Matrix &b) const {
Matrix c(n, m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
c.a[i][j] = ((long long)a[i][j] + b.a[i][j]) % mod;
}
}
return c;
}
Matrix operator+=(const Matrix &b) {
return *this = *this + b;
}
Matrix operator*(const Matrix &b) const {
Matrix c(n, b.m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < b.m; j++) {
for (int k = 0; k < m; k++) {
c.a[i][j] = ((((long long)a[i][k] * b.a[k][j]) % mod) + c.a[i][j]) % mod;
}
}
}
return c;
}
Matrix operator*=(const Matrix &b) {
return *this = *this * b;
}
Matrix operator^(long long k) const {
Matrix t = *this, ans(n);
while (k) {
if (k & 1) {
ans *= t;
}
t *= t;
k >>= 1;
}
return ans;
}
Matrix operator^=(long long k) {
return *this = *this ^ k;
}
};
