Submission

Score: 50

User: Nagornz

Problemset: Tiles

Language: cpp

Time: 0.049 second

Submitted On: 2025-07-12 23:27:21

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));

const int mod = 1e9 + 7;
const int inf = 1e18;

matrix multiply(matrix a, matrix b){
    matrix ans = mat(a.size(), b[0].size());
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b[0].size(); j++) {
            for (int k = 0; k < a[0].size(); k++) {
                ans[i][j] += a[i][k] * b[k][j];
                ans[i][j] %= mod;
            }
        }
    }
    return ans;
}

matrix power(matrix a, int n){
    matrix ans = mat(a.size(), a.size());
    for (int i = 0; i < a.size(); i++) ans[i][i] = 1;
    while (n > 0) {
        if (n % 2) ans = multiply(ans, a);
        a = multiply(a, a);
        n /= 2;
    }
    return ans;
}

void solve(){
    int n, k; cin >> n >> k;
    matrix a = mat(1, 3);
    a[0][0] = 1, a[0][1] = k + 1, a[0][2] = 3 * k + k + 1;
    if (n <= 3) return cout << a[0][n - 1] << "\n", void();
    matrix m = mat(3, 3);
    m[1][0] = 1;
    m[2][1] = 1;
    m[0][2] = 2*k, m[1][2] = k, m[2][2] = 1;
    matrix temp = power(m, n - 3);
    // for (int i = 0; i < 3; i++) {
    //     for (int j = 0; j < 3; j++) cout << temp[i][j] << " ";
    //     cout << "\n";
    // }
    matrix ans = multiply(a, temp);
    cout << ans[0][2] << '\n';
}

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