Submission

Score: 0

User: njoop

Problemset: Tiles

Language: cpp

Time: 0.002 second

Submitted On: 2025-07-10 17:18:22

#include <bits/stdc++.h>
#define int long long
#define vvi vector<vector<int>>
using namespace std;

vvi mat, val, id;
int mod = 1e9+7;

vvi mul(vvi a, vvi b) {
    int axsz = a.size();
    int aysz = a[0].size();
    int bxsz = b.size();
    int bysz = b[0].size();
    vvi out;
    if(aysz != bxsz) {
        cout << "Matrix can't be multiplied";
        exit(0);
    } 
    out.assign(axsz, vector<int>(bysz, 0));
    for(int i=0; i<axsz; i++) {
        for(int j=0; j<bysz; j++) {
            for(int k=0; k<aysz; k++) {
                out[i][j] += a[i][k] * b[k][j];
                out[i][j] %= mod;
            } 
        }
    }
    return out;
}

vvi pow(vvi val, int exp) {
    vvi cmat = val;
    val = id;
    while(exp > 0) {
        if(exp % 2 == 1) {
            val = mul(val, cmat);
        }
        exp /= 2;
        cmat = mul(cmat, cmat);
    }
    return val;
}

void solve() {
    int n, k;
    cin >> n >> k;
    k %= mod;
    id = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
    mat = {{1, k, 2*k}, {1, 0, 0}, {0, 1, 0}};
    val = {{2*k}, {1}, {1}};
    vvi ans = mul(pow(mat, n), val);
    cout << ans[2][0] << "\n";
}

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