Matrix Exponentiation

///M*Fn = Fn+1
struct Matrix {
    const static int N = 3;
    int n;
    int v[N][N];

    void init(int _n) {
        n = _n;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                v[i][j] = 0;
            }
        }
    }
    void ident() {
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                v[i][j] = 0;
            }
        }
        for(int i=0;i<n;i++){
            v[i][i] = 1;
        }
    }

    Matrix operator+(const Matrix &o) const {
        assert(n == o.n);

        Matrix res; res.init(n);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                res.v[i][j] = v[i][j] + o.v[i][j];
                if (res.v[i][j] >= mod) res.v[i][j] -= mod;
            }
        }
        return res;
    }

    Matrix operator*(const Matrix &o) const {
        assert(n == o.n);
        Matrix res; res.init(n);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<n;k++){
                    res.v[i][j] = (v[i][k] * o.v[k][j] + res.v[i][j])%mod;
                }
            }
        }
        return res;
    }

    Matrix operator^(long long k) {
        Matrix res; res.init(n); res.ident();
        Matrix a = *this;
        while (k) {
            if (k&1LL) res = res*a;
            a = a*a;
            k /= 2;
        }
        return res;
    }
};