C++ Quick Pow & Matrix Quick Pow Template

/*
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 res = 1;
    while (b) {
        if (b & 1) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

// 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;
    }
};