题目大意：

 

思路：

　　看到这么高的数据复杂度肯定要log级别的算法才可以过，所以肯定有递推公式，我们可以从一个数字递推一下看当前数字可以转移到哪几个数字，很容易发现出现了一个递推矩阵，再看2个数字的情况，也是一样的，但是要注意不要重复判定就行，就比如4-16-26-46-66-46这样就会出现环，出现环就结束就行了，所以也可以写出2个数字的递推式，所以就可以构造一个递推矩阵。能水过96分，但是大于等于3的情况比较多，先记录一下，以后推出来补充

代码：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
int v2id[70];
int b_e[]={1,2,4,6,16,26,41,42,44,46,61,62,64,66};
int f_t[][4]={{2},{4},{1,6,16},{6,4,64},{26},{46},{62},{64},{61},{66},{42},{44},{41},{46}};
const int mod=998244353;
vector<vector<ll>> mul(vector<vector<ll>> a,vector<vector<ll>> b){
    int n=a.size();
    int kk=a[0].size();
    int m=b[0].size();
    vector<vector<ll>> res(n,vector<ll>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<kk;k++){
                res[i][j]+=((a[i][k]*1ll*b[k][j])%mod);
                res[i][j]=res[i][j]%mod;
            }
        }
    }
    return res;
}

vector<vector<ll>> qmi(vector<vector<ll>> a,int n){
    int r=a.size();
    vector<vector<ll>> res(1,vector<ll>(r,0));
    res[0][0]=1;//把2置为1表示第一个状态 然后快速幂就行了
    
    while(n){
        if(n&1)res=mul(res,a);
        a=mul(a,a);
        n>>=1;
    }
    return res;
}


ll slove(int id,int n){
    vector<vector<ll>> a(14,vector<ll>(14,0));
    for(int i=0;i<14;i++){
        for(int j=0;j<=3;j++){
            if(f_t[i][j]==0)break;
            a[i][v2id[f_t[i][j]]]++;
        }
    }
    vector<vector<ll>> res=qmi(a,n);
    return res[0][id]%mod;
}

int main(){
    memset(v2id,-1,sizeof v2id);
    for(int i=0;i<14;i++){
        v2id[b_e[i]]=i;
    }
    int n;
    string s;
    cin>>n>>s;
    int num=0;
    for(int i=0;i<s.size();i++){
        num*=10;
        num+=(s[i]-'0');
    }
    if(s.size()<=2)cout<<slove(v2id[num],n)<<endl;
    else {
        // 还有一个测试样例不知道咋搞递推式
    }
}