Matrix Fundamentals

struct Mat {
    static const LL M = 2;
    LL v[M][M];
    Mat() { memset(v, 0, sizeof v); }
    void eye() { for (int i = 0; i < M; ++i) v[i][i] = 1; }
    LL* operator [] (LL x) { return v[x]; }
    const LL* const operator [] (LL x) const { return v[x]; }
    Mat operator * (const Mat& B) {
        const Mat& A = *this;
        Mat ret;
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < M; ++j)
                 for (int k = 0; k < M; ++k)
                      ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
        return ret;
    }
    Mat pow(LL n) const {
        Mat A = *this, ret; ret.eye();
        for (; n; n >>= 1, A = A * A)
            if (n & 1) ret = ret * A;
        return ret;
    }
    Mat operator + (const Mat& B) {
        const Mat& A = *this;
        Mat ret;
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < M; ++j)
                 ret[i][j] = (A[i][j] + B[i][j]) % MOD;
        return ret;
    }
    void prt() const {
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < M; ++j)
                 printf("%lld%c", (*this)[i][j], j == M - 1 ? '\n' : ' ');
    }
};