Submission

Score: 100

User: Mingyuanz

Problemset: Tiles

Language: cpp

Time: 0.018 second

Submitted On: 2025-07-13 11:35:23

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,bmi,bmi2")
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define INF (int)2e18
#define MOD (int)(1e9+7)
#define MAXN 200005
#define enl '\n'
#define DB(CODE) cout<<'\t'<<CODE<<'\n';
#define SP <<' '<<
#define int long long
#define mat vector<vector<int>>
#define newmat(n,m) vector<vector<int>>(n,vector<int>(m))
#define sz(v) (int)v.size()
#define printmat(A) for(auto x:A){for(auto y:x)cout<<y<<" ";cout<<'\n';}
typedef long long ll;
using namespace std;
mat matpow(mat &A,int n){
    if(n==1) return A;
    mat P=matpow(A,n/2);
    mat B=newmat(3,3);
    for(int i=0; i<3; i++) for(int j=0; j<3; j++) for(int k=0; k<3; k++) B[i][j]=(B[i][j]+P[i][k]*P[k][j]%MOD)%MOD;
    if(n%2){
        P=newmat(3,3);
        for(int i=0; i<3; i++) for(int j=0; j<3; j++) for(int k=0; k<3; k++) P[i][j]=(P[i][j]+B[i][k]*A[k][j]%MOD)%MOD;
        return P;
    } return B;
}
void testcase(){
    int n,k;
    cin >> n >> k;
    k%=MOD;
    if(n==0) return (void)(cout << 1 << enl);
    if(n==1) return (void)(cout << 1 << enl);
    if(n==2) return (void)(cout << (1+k)%MOD << enl);
    mat A={{1,k%MOD,2*k%MOD},{1,0,0},{0,1,0}};
    mat X={{(1+k)%MOD},{1},{1}};
    mat P=matpow(A,n-2);
    cout << ((P[0][0]*X[0][0]%MOD+P[0][1]*X[1][0]%MOD)%MOD+P[0][2]*X[2][0]%MOD)%MOD << enl;
}
signed main(){
    cin.tie(0)->sync_with_stdio(false);
    int t=1;
    cin >> t;
    while(t--){
        testcase();
    }
    return 0;
}