Submission

Score: 100

User: Dormon

Problemset: Tiles

Language: cpp

Time: 0.032 second

Submitted On: 2025-07-10 18:50:19

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

struct Matrix {
    vector<vector<ll>> a;
    int row, col;
    Matrix(int n, int m) : row(n), col(m), a(n, vector<ll>(m, 0ll)) {}
    Matrix(int n) : Matrix(n, n) {}
    friend Matrix operator * (const Matrix &lhs, const Matrix &rhs){
        int n = lhs.row, m = lhs.col, o = rhs.col;
        Matrix res(n, o);
        for (int i = 0;i < n;i++)
            for (int j = 0;j < o;j++)
                for (int k = 0;k < m;k++)
                    res.a[i][j] = (res.a[i][j] + (lhs.a[i][k] * rhs.a[k][j]) % mod) % mod;
        return res;
    }
    friend ostream &operator << (ostream &out, const Matrix &o){
        int n = o.row, m = o.col;
        for (int i = 0;i < n;i++){
            for (int j = 0;j < m;j++)
                out << o.a[i][j] << ' ';
            out << '\n';
        }
        cout << string(10, '-') << '\n';
        return out;
    }
};

Matrix binpow(Matrix b, ll n){
    Matrix res(b.row);
    for (int i = 0;i < b.row;i++) res.a[i][i] = 1ll;
    while (n > 0ll){
        if (n & 1ll) res = res * b;
        b = b * b;
        n >>= 1ll;
    }
    return res;
}

void solve(){
    ll n, k;
    cin >> n >> k;
    k %= mod;
    if (n <= 3){
        vector<ll> ans = {1, k + 1ll, 4 * k + 1ll};
        cout << ans[n - 1] % mod << '\n';
        return ;
    }
    Matrix base(3);
    base.a[1][0] = base.a[2][1] = 1ll;
    base.a[0][2] = 2ll * k;
    base.a[1][2] = k;
    base.a[2][2] = 1ll;
    Matrix res(1, 3);
    res.a[0][0] = 1ll;
    res.a[0][1] = k + 1;
    res.a[0][2] = 4ll * k + 1;
    Matrix dp = binpow(base, n - 3);
    Matrix ans = res * dp;
    cout << ans.a[0][2] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int q;
    cin >> q;
    while (q--){
        solve();
    }
}