萌新求问

#include <bits/stdc++.h>
using namespace std;
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define fir first
#define sec second
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ll long long
#define int long long
const int maxn=1e5+10;
const int mod=1e9+7;
int num[maxn];
int dp[maxn][2];
int dfs(int pos,bool is1,bool lim,bool zer)
{
    if(pos==0) return 1;
    if(!lim&&!zer&&dp[pos][is1]!=-1) return dp[pos][is1];
    int cnt=0;
    REP(i,zer,(lim?num[pos]:9))
    if(is1&&i==3);
    else
    {
        cnt+=dfs(pos-1,(i==1),(lim&&i==num[pos]),0);
        cnt%=mod;
    }
    if(!lim&&!zer) dp[pos][is1]=cnt;
    return cnt;
}
string x;
void solve(int l,int r)
{
    while(x[l]=='0') l++;
    int tot=0;
    for(int i=r;i>=l;i--) num[++tot]=x[i]-'0';
    int ans=dfs(tot,0,1,1);
    REP(i,1,tot-1) ans+=dfs(i,0,0,1),ans%=mod;
    cout<<ans+1<<"\n";
}
signed main()
{
    Ios();
    memset(dp,-1,sizeof dp);
    int n,q;
    cin>>n>>q>>x;
    x=" "+x;
    solve(1,n);
    while(q--)
    {
        int opt;
        cin>>opt;
        if(opt==1)
        {
            int l,r;
            cin>>l>>r;
            solve(l,r);
        }
        else
        {
            int p,v;
            cin>>p>>v;
            x[p]=v+'0';
        }
    }
}

#include <bits/stdc++.h>
using namespace std;
void Ios(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define fir first
#define sec second
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ll long long
#define int long long
const int maxn=1e5+10;
const int mod=1e9+7;
int num[maxn];
int dp[maxn][2];
int dfs(int pos,bool is1,bool lim)
{
    if(pos==0) return 1;
    if(!lim&&dp[pos][is1]!=-1) return dp[pos][is1];
    int cnt=0;
    REP(i,0,(lim?num[pos]:9))
    if(is1&&i==3);
    else
    {
        cnt+=dfs(pos-1,(i==1),(lim&&i==num[pos]));
        cnt%=mod;
    }
    if(!lim) dp[pos][is1]=cnt;
    return cnt;
}
string x;
void solve(int l,int r)
{
    while(x[l]=='0') l++;
    int tot=0;
    for(int i=r;i>=l;i--) num[++tot]=x[i]-'0';
    int ans=dfs(tot,0,1);
    cout<<ans<<"\n";
}
signed main()
{
    Ios();
    memset(dp,-1,sizeof dp);
    int n,q;
    cin>>n>>q>>x;
    x=" "+x;
    solve(1,n);
    while(q--)
    {
        int opt;
        cin>>opt;
        if(opt==1)
        {
            int l,r;
            cin>>l>>r;
            solve(l,r);
        }
        else
        {
            int p,v;
            cin>>p>>v;
            x[p]=v+'0';
        }
    }
}