#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1'000'000'007;   // can be changed per problem

// ===============================
// 1) Matrix definition and basic operations
// ===============================

/**
 * Struct: Matrix
 * Purpose: Represents a matrix of size n x m with long long entries.
 * Usage: Matrix M(n, m); or Matrix M(n, m, data); where data is a 2D vector.
 * Notes: All arithmetic is done modulo MOD.
 *        - The multiplication operator (*) performs matrix multiplication.
 *        - The operator* with vector multiplies matrix by a column vector.
 *        - identity(size) creates an identity matrix.
 * Constraints: n, m >= 0. For multiplication, dimensions must agree.
 * Time Complexity:
 *   - Constructor: O(n*m)
 *   - identity: O(size^2)
 *   - Multiplication (Matrix*Matrix): O(n * m * other.m) with skip-if-zero optimisation.
 *   - Multiplication (Matrix*Vector): O(n * m)
 */
struct Matrix {
    int n, m;                 // dimensions (n rows, m columns)
    vector<vector<ll>> a;     // data

    Matrix(int n_ = 0, int m_ = 0) : n(n_), m(m_) {
        a.assign(n, vector<ll>(m, 0));
    }

    Matrix(int n_, int m_, const vector<vector<ll>>& data) : n(n_), m(m_), a(data) {}

    // Creates an identity matrix (square)
    static Matrix identity(int size) {
        Matrix I(size, size);
        for (int i = 0; i < size; ++i) I.a[i][i] = 1;
        return I;
    }

    // Matrix multiplication (with modulo)
    Matrix operator*(const Matrix& other) const {
        if (m != other.n) throw invalid_argument("Incompatible dimensions for multiplication");
        Matrix res(n, other.m);
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < m; ++k) {
                if (a[i][k] == 0) continue;      // small optimisation
                for (int j = 0; j < other.m; ++j) {
                    res.a[i][j] = (res.a[i][j] + a[i][k] * other.a[k][j]) % MOD;
                }
            }
        }
        return res;
    }

    // Multiply matrix by a column vector
    vector<ll> operator*(const vector<ll>& vec) const {
        if (m != (int)vec.size()) throw invalid_argument("Vector size mismatch");
        vector<ll> res(n, 0);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                res[i] = (res[i] + a[i][j] * vec[j]) % MOD;
            }
        }
        return res;
    }

    // Print the matrix (for testing)
    void print() const {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) cout << a[i][j] << ' ';
            cout << '\n';
        }
    }
};

// ===============================
// 2) Fast exponentiation of matrices
// ===============================

/**
 * Function: matPow
 * Purpose: Raise a square matrix to a non‑negative integer exponent (binary exponentiation).
 * Usage: Matrix result = matPow(base, exponent);
 * Time Complexity: O(log(exponent) * n^3) where n is the matrix dimension.
 * Notes: The matrix must be square.
 * Constraints: exponent >= 0.
 */
Matrix matPow(Matrix base, ll exponent) {
    if (base.n != base.m) throw invalid_argument("Matrix must be square");
    Matrix result = Matrix::identity(base.n);
    while (exponent > 0) {
        if (exponent & 1) result = result * base;
        base = base * base;
        exponent >>= 1;
    }
    return result;
}

// ===============================
// 3) Direct applications: linear recurrences
// ===============================

/**
 * Function: fib
 * Purpose: Compute the n-th Fibonacci number (F_0 = 0, F_1 = 1).
 * Usage: ll ans = fib(n);
 * Time Complexity: O(log n) because matrix is 2x2.
 * Notes: Result is modulo MOD. Uses a transition matrix.
 * Constraints: n >= 0.
 */
ll fib(ll n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    Matrix T(2, 2);
    T.a = {{1, 1}, {1, 0}};   // transition matrix
    Matrix Tn = matPow(T, n - 1);
    vector<ll> initial = {1, 0};   // [F_1, F_0]^T
    vector<ll> result = Tn * initial;
    return result[0];
}

/**
 * Function: tribonacci
 * Purpose: Compute the n-th Tribonacci number (T_0=0, T_1=0, T_2=1).
 * Usage: ll ans = tribonacci(n);
 * Time Complexity: O(log n) with 3x3 matrix.
 * Notes: Modulo MOD.
 * Constraints: n >= 0.
 */
ll tribonacci(ll n) {
    if (n == 0 || n == 1) return 0;
    if (n == 2) return 1;
    Matrix T(3, 3);
    T.a = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};
    Matrix Tn = matPow(T, n - 2);
    vector<ll> initial = {1, 0, 0};   // [T_2, T_1, T_0]^T
    vector<ll> res = Tn * initial;
    return res[0];
}

/**
 * Function: linearRecurrence
 * Purpose: Compute the n-th term of a general linear recurrence of order k:
 *          f(n) = c[0]*f(n-1) + c[1]*f(n-2) + ... + c[k-1]*f(n-k)
 * Usage: ll ans = linearRecurrence(initial, coeff, n);
 *        - initial: vector of size k with f(0), f(1), ..., f(k-1)
 *        - coeff:   vector of size k with c[0], c[1], ..., c[k-1]
 *        - n:       the index to compute (n >= 0)
 * Time Complexity: O(k^3 log n) because matrix is k x k.
 * Notes: Uses the companion matrix. All computations modulo MOD.
 * Constraints: k >= 1, n >= 0.
 */
ll linearRecurrence(const vector<ll>& initial, const vector<ll>& coeff, ll n) {
    int k = initial.size();
    if (n < k) return initial[n] % MOD;

    // Build companion matrix
    Matrix T(k, k);
    for (int j = 0; j < k; ++j) T.a[0][j] = coeff[j] % MOD;
    for (int i = 1; i < k; ++i) {
        T.a[i][i-1] = 1;
    }

    Matrix Tn = matPow(T, n - k + 1);
    vector<ll> initVec(k);
    for (int i = 0; i < k; ++i) initVec[i] = initial[i] % MOD;

    vector<ll> res = Tn * initVec;
    return res[0];
}

// ===============================
// 4) Counting walks in a graph
// ===============================

/**
 * Function: countWalks
 * Purpose: Count the number of walks of length k from node s to node t in an unweighted directed graph.
 * Usage: ll ans = countWalks(adj, s, t, k);
 *        - adj: adjacency matrix (n x n) where adj.a[i][j] = 1 if edge i->j exists.
 *        - s,t: 0‑based node indices.
 *        - k:    length of the walk (number of edges).
 * Time Complexity: O(log k * n^3) because we raise the adjacency matrix to power k.
 * Notes: Works for both directed and undirected (if symmetric). Result modulo MOD.
 * Constraints: adj must be square; k >= 0.
 */
ll countWalks(const Matrix& adj, int s, int t, ll k) {
    if (adj.n != adj.m) throw invalid_argument("Adjacency matrix must be square");
    Matrix Ak = matPow(adj, k);
    return Ak.a[s][t] % MOD;
}

// ===============================
// 5) Sum of first terms of a linear recurrence
// ===============================

/**
 * Function: sumFirstNFib
 * Purpose: Compute S(n) = F_0 + F_1 + ... + F_n (sum of first n+1 Fibonacci numbers).
 * Usage: ll ans = sumFirstNFib(n);
 * Time Complexity: O(log n) with a 3x3 augmented matrix.
 * Notes: n >= 0. Result modulo MOD.
 *        The augmented matrix includes the cumulative sum as a state.
 */
ll sumFirstNFib(ll n) {
    if (n == 0) return 0;
    Matrix T(3, 3);
    T.a = {{1, 1, 0}, {1, 0, 0}, {1, 1, 1}};
    Matrix Tn = matPow(T, n);
    vector<ll> initial = {1, 0, 0};  // F_1=1, F_0=0, S_0=0
    vector<ll> res = Tn * initial;
    return res[2];  // S_n
}

// The same idea can be generalised to any linear recurrence by adding a row for the sum.

// ===============================
// 6) Advanced improvements and tricks
// ===============================

/**
 * Function: vecPow
 * Purpose: Compute (base^exp) * vec efficiently without multiplying matrices together at each step.
 * Usage: vector<ll> result = vecPow(base, vec, exp);
 *        - base: square matrix
 *        - vec:  initial column vector
 *        - exp:  exponent (non‑negative)
 * Time Complexity: O(log exp * n^2) because we multiply matrix by vector (O(n^2)) instead of matrix*matrix (O(n^3)).
 * Notes: This is faster when only the final vector is needed and the vector size is small.
 *        The matrix must be square.
 * Constraints: exp >= 0, vec size = base.n.
 */
vector<ll> vecPow(Matrix base, vector<ll> vec, ll exp) {
    while (exp > 0) {
        if (exp & 1) vec = base * vec;
        base = base * base;
        exp >>= 1;
    }
    return vec;
}

// Other tricks (sparse matrices, Kitamasa, Berlekamp‑Massey) are included below.

/**
 * Function: combine
 * Purpose: Helper for Kitamasa method: multiply two polynomials modulo the characteristic polynomial.
 * Usage: vector<ll> res = combine(a, b, coeff);
 *        - a, b: polynomials as vectors of coefficients (length k)
 *        - coeff: recurrence coefficients (c[0..k-1]) such that
 *                 x^k = coeff[0]*x^(k-1) + ... + coeff[k-1]
 * Time Complexity: O(k^2)
 * Notes: Internal function used by kitamasa.
 */
vector<ll> combine(const vector<ll>& a, const vector<ll>& b, const vector<ll>& coeff) {
    int k = coeff.size();
    vector<ll> res(2 * k, 0);
    for (int i = 0; i < k; i++)
        for (int j = 0; j < k; j++)
            res[i + j] = (res[i + j] + a[i] * b[j]) % MOD;

    for (int i = 2*k - 2; i >= k; i--) {
        for (int j = 1; j <= k; j++)
            res[i - j] = (res[i - j] + res[i] * coeff[j-1]) % MOD;
    }
    res.resize(k);
    return res;
}

/**
 * Function: kitamasa
 * Purpose: Compute the n-th term of a linear recurrence using Kitamasa's algorithm (O(k^2 log n)).
 * Usage: ll ans = kitamasa(n, init, coeff);
 *        - n: index to compute (n >= 0)
 *        - init: initial terms f(0)..f(k-1)
 *        - coeff: recurrence coefficients (same order as in linearRecurrence)
 * Time Complexity: O(k^2 log n)
 * Notes: Faster than matrix exponentiation when k is large (e.g., k up to a few thousand).
 *        This method avoids matrix multiplication and works with polynomial exponents.
 * Constraints: k >= 1, n >= 0.
 */
ll kitamasa(ll n, const vector<ll>& init, const vector<ll>& coeff) {
    int k = coeff.size();
    if (n < k) return init[n] % MOD;

    vector<ll> pol(k, 0), e(k, 0);
    pol[0] = 1;       // represents x^0
    // initialise e to represent x^1
    if (k == 1) {
        // For order 1, x ≡ coeff[0] (mod x - coeff[0])
        e[0] = coeff[0] % MOD;
    } else {
        e[1] = 1;      // x^1
    }

    while (n) {
        if (n & 1) pol = combine(pol, e, coeff);
        e = combine(e, e, coeff);
        n >>= 1;
    }

    ll ans = 0;
    for (int i = 0; i < k; i++)
        ans = (ans + pol[i] * init[i]) % MOD;
    return ans;
}

// ===============================
// 7) Sparse Matrix Exponentiation using Berlekamp‑Massey + Kitamasa
// ===============================

/**
 * Function: modPow
 * Purpose: Fast modular exponentiation (a^e % MOD).
 * Usage: ll result = modPow(a, e);
 * Time Complexity: O(log e)
 */
ll modPow(ll a, ll e) {
    ll res = 1;
    a %= MOD;
    while (e > 0) {
        if (e & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return res;
}

/**
 * Function: modInv
 * Purpose: Modular inverse of a modulo MOD (MOD must be prime).
 * Usage: ll inv = modInv(a);
 * Time Complexity: O(log MOD)
 */
ll modInv(ll a) {
    return modPow(a, MOD - 2);
}

/**
 * Function: dot
 * Purpose: Dot product of two vectors modulo MOD.
 * Usage: ll val = dot(a, b);
 * Time Complexity: O(n)
 */
ll dot(const vector<ll>& a, const vector<ll>& b) {
    ll res = 0;
    for (size_t i = 0; i < a.size(); i++)
        res = (res + a[i] * b[i]) % MOD;
    return res;
}

/**
 * Function: berlekamp_massey
 * Purpose: Given the first terms of a linearly recurrent sequence, find the minimal recurrence coefficients.
 * Usage: vector<ll> coeff = berlekamp_massey(s);
 *        - s: vector of initial sequence values (length at least 2 * expected order)
 * Returns: coefficients [c0, c1, ..., cL] such that s[n] = sum_{j=1..L} coeff[j] * s[n-j]
 * Time Complexity: O(L^2) where L is the order found.
 * Notes: This is the Berlekamp‑Massey algorithm. It works modulo MOD.
 *        The returned vector has length L+1 (with constant term = 1, reversed internally).
 * Constraints: MOD must be prime for modular inverse; s must be long enough.
 */
vector<ll> berlekamp_massey(const vector<ll>& s) {
    vector<ll> C(1, 1), B(1, 1);
    ll b = 1; int L = 0, m = 1;
    for (int n = 0; n < (int)s.size(); n++) {
        ll d = s[n];
        for (int i = 1; i <= L; i++)
            d = (d + C[i] * s[n - i]) % MOD;
        if (d == 0) { m++; continue; }
        vector<ll> T = C;
        ll coef = d * modInv(b) % MOD;   // modInv is now defined
        if (C.size() < B.size() + m) C.resize(B.size() + m, 0);
        for (int j = 0; j < (int)B.size(); j++)
            C[j + m] = (C[j + m] - coef * B[j]) % MOD;
        if (2 * L <= n) {
            L = n + 1 - L;
            B = T;
            b = d;
            m = 1;
        } else m++;
    }
    C.resize(L + 1);
    reverse(C.begin(), C.end()); // now coefficients for recurrence
    return C;
}

/**
 * Function: sparseMatPow
 * Purpose: Compute a^T * M^k * b for a sparse matrix M, using Berlekamp‑Massey + Kitamasa.
 * Usage: ll result = sparseMatPow(M, a, b, k);
 *        - M: square sparse matrix (n x n)
 *        - a, b: vectors of size n (column vectors)
 *        - k: exponent (non‑negative)
 * Time Complexity: O(n * nnz + L^2 log k) where nnz is number of non‑zero entries in M,
 *                  and L is the order of the recurrence (≤ n).
 * Notes: This is efficient for large n but sparse M. It first generates the sequence
 *        s[i] = a^T * M^i * b for i=0..2n, finds the linear recurrence via Berlekamp‑Massey,
 *        then computes s[k] using Kitamasa.
 *        NOTE: The current implementation multiplies M by a vector using dense O(n^2)
 *        because Matrix uses dense storage. For true sparse efficiency, you should replace
 *        `cur = M * cur` with a sparse multiplication routine.
 * Constraints: M must be square; n >= 1; k >= 0.
 */
ll sparseMatPow(const Matrix& M, const vector<ll>& a, const vector<ll>& b, ll k) {
    int n = M.n;
    vector<ll> s(2 * n + 1);
    vector<ll> cur = b;
    for (int i = 0; i <= 2*n; i++) {
        s[i] = dot(a, cur);   // dot is now defined
        cur = M * cur;        // O(n^2) – replace with sparse version if needed
    }
    vector<ll> coeff = berlekamp_massey(s); // recurrence coefficients
    // coeff: c0, c1, ..., cL such that s[i] = sum_{j=1..L} coeff[j] * s[i-j]
    return kitamasa(k, s, coeff);
}

// ===============================
// 8) Precomputation of matrix powers for multiple queries
// ===============================

/**
 * Function: precomputePowers
 * Purpose: Precompute powers of a matrix up to a given maximum exponent (for fast queries).
 * Usage: vector<Matrix> powers = precomputePowers(base, maxExp);
 *        - base: square matrix
 *        - maxExp: maximum exponent to support (exclusive, i.e., 2^(maxExp-1) <= maxExp)
 * Time Complexity: O(log(maxExp) * n^3)
 * Notes: The vector powers[i] = base^(2^i). Used with applyPower.
 */
vector<Matrix> precomputePowers(Matrix base, ll maxExp) {
    vector<Matrix> powers;
    powers.push_back(base);
    for (int i = 1; (1LL << i) <= maxExp; i++)
        powers.push_back(powers.back() * powers.back());
    return powers;
}

/**
 * Function: applyPower
 * Purpose: Apply a precomputed power to an initial vector.
 * Usage: vector<ll> result = applyPower(powers, exp, init);
 *        - powers: vector from precomputePowers
 *        - exp:    exponent to apply (non‑negative)
 *        - init:   initial column vector
 * Time Complexity: O(log exp * n^2) because we multiply matrix*vector.
 * Notes: This is faster for many queries with different exponents after one precomputation.
 * Constraints: exp >= 0; exp must fit in the precomputed range.
 */
vector<ll> applyPower(const vector<Matrix>& powers, ll exp, const vector<ll>& init) {
    vector<ll> cur = init;
    int bit = 0;
    while (exp > 0) {
        if (exp & 1) cur = powers[bit] * cur;
        exp >>= 1;
        bit++;
    }
    return cur;
}

// ===============================
// 9) Test functions (simple examples)
// ===============================

void testFibonacci() {
    cout << "Testing Fibonacci:\n";
    for (int i = 0; i <= 10; i++)
        cout << "F(" << i << ") = " << fib(i) << "\n";
    cout << "\n";
}

void testLinearRecurrence() {
    cout << "Testing linear recurrence (Fibonacci):\n";
    vector<ll> init = {0, 1};      // F0=0, F1=1
    vector<ll> coeff = {1, 1};     // F(n) = 1*F(n-1) + 1*F(n-2)
    for (int n = 0; n <= 10; n++)
        cout << "F(" << n << ") = " << linearRecurrence(init, coeff, n) << "\n";
    cout << "\n";
}

// ===============================
// 10) Example usage
// ===============================

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Quick tests
    testFibonacci();
    testLinearRecurrence();

    // Example: counting walks in a simple graph
    // Graph with edges: 0->1, 1->0, 1->2
    Matrix adj(3, 3);
    adj.a = {{0, 1, 0}, {1, 0, 1}, {0, 1, 0}};
    ll paths = countWalks(adj, 0, 2, 3);  // length 3
    cout << "Walks from 0 to 2 of length 3: " << paths << '\n';

    // Example: using vecPow for faster Fibonacci
    Matrix T(2, 2);
    T.a = {{1, 1}, {1, 0}};
    vector<ll> init = {1, 0};  // F_1, F_0
    vector<ll> res = vecPow(T, init, 9);   // computes F_10
    cout << "F_10 via vecPow = " << res[0] << '\n';

    return 0;
}