下面这段代码对应的 bas 的次数是 n-1，而非oiwiki上提到的 n-2，虽然使用的矩阵一样，但是为什么仍可以通过。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct M {
    int n, m;
    int mat[107][107];
    M() {
        memset(mat, 0, sizeof(mat));
    }
} bas, ori;
int n, T, m, MOD;
M mul(M a, M b) {//矩阵乘法
    M ans;
    ans.n = a.n, ans.m = b.m;
    for(int i = 1; i <= ans.n; i++) {
        for(int j = 1; j <= ans.m; j++) {
            for(int k = 1; k <= a.m; k++) {
                ans.mat[i][j] = (ans.mat[i][j] + 1ll * a.mat[i][k] * b.mat[k][j])% MOD;
            }
        }
    }
    return ans;
}
M qpow(M x, ll p) {//矩阵快速幂
    M ret;
    ret.n = ret.m = x.n;
    for(int i = 1; i <= x.n; i++) ret.mat[i][i] = 1;
    while(p) {
        if(p & 1) ret = mul(ret, x);
        p >>= 1;
        x = mul(x, x);
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    //初始化矩阵
    bas.n=bas.m=2;
    ori.n=1,ori.m=2;
    bas.mat[1][1]=bas.mat[1][2]=bas.mat[2][1]=1;
    ori.mat[1][1]=ori.mat[1][2]=1;
    cin >> T;
    while(T--) {
        cin >> n >> m;
        if(n <= 2) {
            cout << 1<< "\n";
        } else {
            MOD=1<<m;
            M ans=qpow(bas,n-1);
            ans=mul(ori,ans);
            cout<<ans.mat[1][1]%MOD<<"\n";
        }
    }
    return 0;
}