#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
const int mod = 1e9 + 7, N = 1e5;
const int mod2 = mod * mod;
string s;
int p10[2][2][N + 5];
struct nod
{
int dp[2][2];
int cifrafata, cifraspate, are13, lg;
};
nod aint[4 * N + 5];
void print(nod x)
{
}
nod cif(int x)
{
nod a;
a.dp[0][0] = x;
if(x > 3)
a.dp[1][0] = 1;
else
a.dp[1][0] = 0;
if(x > 1)
a.dp[0][1] = 1;
else
a.dp[0][1] = 0;
a.dp[1][1] = 0;
a.cifrafata = x;
a.cifraspate = x;
a.are13 = 0;
a.lg = 1;
return a;
}
nod join(nod a, nod b)
{
nod c;
c.cifrafata = a.cifrafata;
c.cifraspate = b.cifraspate;
if(a.cifraspate == 1 && b.cifrafata == 3)
c.are13 = 1;
else
c.are13 = (a.are13 | b.are13);
c.lg = a.lg + b.lg;
for(auto i : {0, 1})
for(auto j : {0, 1})
{
if(a.are13)
c.dp[i][j] = (a.dp[i][0] * p10[0][j][b.lg] - a.dp[i][1] * p10[1][j][b.lg] + mod2) % mod;
else
{
if(a.cifraspate == 1)
c.dp[i][j] = (a.dp[i][0] * p10[0][j][b.lg] - a.dp[i][1] * p10[1][j][b.lg] + b.dp[0][j] - b.dp[1][j] + mod2) % mod;
else
c.dp[i][j] = (a.dp[i][0] * p10[0][j][b.lg] - a.dp[i][1] * p10[1][j][b.lg] + b.dp[0][j] + mod2) % mod;
}
}
return c;
}
#define mid (st + dr) / 2
void update(int pos, int st, int dr, int l, int val)
{
if(st == dr)
{
aint[pos] = cif(val);
return;
}
if(l <= mid)
update(2 * pos, st, mid, l, val);
else
update(2 * pos + 1, mid + 1, dr, l, val);
aint[pos] = join(aint[2 * pos], aint[2 * pos + 1]);
}
nod query(int pos, int st, int dr, int l, int r)
{
if(l <= st && dr <= r)
return aint[pos];
if(r <= mid)
return query(2 * pos, st, mid, l, r);
if(mid < l)
return query(2 * pos + 1, mid + 1, dr, l, r);
return join(query(2 * pos, st, mid, l, r), query(2 * pos + 1, mid + 1, dr, l, r));
}
void build(int pos, int st, int dr)
{
if(st == dr)
{
aint[pos] = cif(s[st] - '0');
return;
}
build(2 * pos, st, mid);
build(2 * pos + 1, mid + 1, dr);
aint[pos] = join(aint[2 * pos], aint[2 * pos + 1]);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
p10[0][0][0] = 1;
p10[0][0][1] = 10;
p10[1][0][1] = 1;
p10[0][1][1] = 1;
p10[1][1][1] = 0;
for(int i = 2; i <= N; i ++)
{
p10[0][0][i] = (p10[0][0][i - 1] * 10 - p10[1][0][i - 1] + mod2) % mod;
p10[1][0][i] = p10[0][0][i - 1];
p10[0][1][i] = p10[0][0][i - 1];
p10[1][1][i] = p10[0][0][i - 2];
}
int n, q;
cin >> n >> q >> s;
s = "#" + s;
build(1, 1, n);
auto x = query(1, 1, n, 1, n);
cout << x.dp[0][0] + 1 - x.are13 << '\n';
for(int i = 0; i < q; i ++)
{
int t, l, r;
cin >> t >> l >> r;
if(t == 1)
{
auto y = query(1, 1, n, l, r);
cout << y.dp[0][0] + 1 - y.are13 << '\n';
}
else
update(1, 1, n, l, r);
}
}
/*
putem face un aint in care sa tinem in stanga nr de numere pe care le putem face fara 13
in dreapta la fel
si mai tinem cate nr fara 13 putem face a.i. ultima cifra sa fie 1
si cate nr fara 13 putem face a.i. ultima cifra sa fie 3
si cred ca ne trebuie si cate putem face a.i. prima cifra sa fie 1 si ultima fie 3
also ne trebuie o precalculare pentru cate numere pana in 10^x nu au 13
cate numere pana in 10^x nu au 13 si au 1 prima cifra si cate numere pana in 10^x nu au 13 si au 3 ultima cifra
fata inseamna sa aiba prima cifra 3 dar nicaieri 13
spate inseamna sa aiba prima cifra 1 dar nicaieri 13
c.nrtotal
daca a are deja 13
a.nrtotal * p10[b.nrcif] - a.spate * p10fata[b.nrcif];
altfel
daca a are ultima cifra 1
a.nrtotal * p10[b.nrcif] - a.spate * p10fata[b.nrcif] + b.nrtotal - b.fata
altfel
a.nrtotal * p10[b.nrcif] - a.spate * p10fata[b.nrcif] + b.nrtotal
c.fata
daca a are deja 13
a.fata * p10[b.nrcif] - a.spate * p10fata[b.nrcif];
altfel
daca a are ultima cifra 1
a.fata * p10[b.nrcif] - a.spate * p10fata[b.nrcif] + b.nrtotal - b.fata
altfel
a.fata * p10[b.nrcif] - a.spate * p10fata[b.nrcif] + b.nrtotal
c.spate
daca a are deja 13
a.nrtotal * p10spate[b.nrcif] - a.spate * p10fataspate[b.nrcif];
altfel
daca a are ultima cifra 1
a.nrtotal * p10spate[b.nrcif] - a.spate * p10fataspate[b.nrcif] + b.spate - b.fataspate
altfel
a.nrtotal * p10spate[b.nrcif] - a.spate * p10fataspate[b.nrcif] + b.spate
c.fataspate
daca a are deja 13
a.fata * p10spate[b.nrcif] - a.fataspate * p10fataspate[b.nrcif];
altfel
daca a are ultima cifra 1
a.fata * p10spate[b.nrcif] - a.fataspate * p10fataspate[b.nrcif] + b.spate - b.fataspate
altfel
a.fata * p10spate[b.nrcif] - a.fataspate * p10fataspate[b.nrcif] + b.spate
*/
