/**
* user: tinca-6db
* fname: Matei
* lname: Tinca
* task: lucky
* score: 100.0
* date: 2019-10-10 09:19:09.769672
*/
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int MAX_N = 100000;
struct IntMod {
int val;
IntMod():val(0) {}
IntMod(int x):val(x % MOD) {}
IntMod operator+(IntMod x) {
if(x.val + val >= MOD)
return x.val + val - MOD;
return x.val + val;
}
IntMod operator*(IntMod x) {
return (long long)x.val * val % MOD;
}
IntMod operator+(int x) {
return (*this) + IntMod(x);
}
IntMod operator*(int x) {
return (*this) * IntMod(x);
}
IntMod operator-(IntMod x) {
return (*this) + (MOD - x.val);
}
IntMod operator-(int x) {
return (*this) - IntMod(x);
}
};
// cate numere bune de forma a1a2...aN exista?
IntMod _goodcnt[1+MAX_N+1], *goodcnt = _goodcnt + 1;
struct AintNode {
int size;
IntMod cntgood, cntgood1, cntgood3, cntgood31;
bool isgood, isgood1, isgood3, isgood31;
};
// cntgood = numar chestii bune pe interval
// cntgood1 = numar chestii bune pe interval care se termina cu 1
// cntgood3 = numar chestii bune pe interval care incep cu 3
// cntgood31 = numar chestii bune pe interval care incep cu 3 si se termina cu 1
AintNode combine(AintNode a, AintNode b) {
AintNode rez;
rez.isgood = a.isgood && b.isgood && !(a.isgood1 && b.isgood3);
rez.isgood1 = b.isgood1 && a.isgood && !(a.isgood1 && b.isgood3);
rez.isgood3 = a.isgood3 && b.isgood && !(a.isgood1 && b.isgood3);
rez.isgood31 = a.isgood3 && b.isgood1 && !(a.isgood1 && b.isgood3);
rez.cntgood = (a.cntgood - a.isgood) * goodcnt[b.size] + b.cntgood * a.isgood -
(a.cntgood1 - a.isgood1) * goodcnt[b.size - 1] - b.cntgood3 * a.isgood1;
rez.cntgood1 = (a.cntgood - a.isgood) * goodcnt[b.size - 1] + b.cntgood1 * a.isgood -
(a.cntgood1 - a.isgood1) * goodcnt[b.size - 2] - b.cntgood31 * a.isgood1;
rez.cntgood3 = (a.cntgood3 - a.isgood3) * goodcnt[b.size] + b.cntgood * a.isgood3 -
(a.cntgood31 - a.isgood31) * goodcnt[b.size - 1] - b.cntgood3 * a.isgood31;
rez.cntgood31 = (a.cntgood3 - a.isgood3) * goodcnt[b.size - 1] + b.cntgood1 * a.isgood3 -
(a.cntgood31 - a.isgood31) * goodcnt[b.size - 2] - b.cntgood31 * a.isgood31;
rez.size = a.size + b.size;
return rez;
}
AintNode aint[1+4*MAX_N];
void update(int poz, AintNode val, int l = 1, int r = MAX_N, int nod = 1) {
if(r < poz || poz < l) return;
if(l == r)
aint[nod] = val;
else {
int mid = (l + r) / 2;
update(poz, val, l, mid, 2 * nod);
update(poz, val, mid + 1, r, 2 * nod + 1);
aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
}
}
AintNode query(int i, int j, int l = 1, int r = MAX_N, int nod = 1) {
if(i <= l && r <= j)
return aint[nod];
else {
int mid = (l + r) / 2;
if(i > mid)
return query(i, j, mid + 1, r, 2 * nod + 1);
else if(j <= mid)
return query(i, j, l, mid, 2 * nod);
else
return combine(query(i, j, l, mid, 2 * nod),
query(i, j, mid + 1, r, 2 * nod + 1));
}
}
void dfs(int nod = 1, int l = 1, int r = MAX_N) {
printf("RANGE: %d %d->%d\n", l, r, nod);
printf("isgood: %d %d %d %d", aint[nod].isgood, aint[nod].isgood1, aint[nod].isgood3, aint[nod].isgood31);
printf("cntgood: %d %d %d %d\n", aint[nod].cntgood.val, aint[nod].cntgood1.val, aint[nod].cntgood3.val, aint[nod].cntgood31.val);
int mid = (l + r) / 2;
if(l < r) {
dfs(2 * nod, l, mid);
dfs(2 * nod + 1, mid + 1, r);
}
}
// AintNode = {size, cntgood, cntgood1, cntgood3, cntgood31, isgood, isgood1, isgood3, isgood31}
AintNode updDigit[10] = {
{1, IntMod(1), IntMod(0), IntMod(0), IntMod(0), true, false, false, false}, // 0
{1, IntMod(2), IntMod(1), IntMod(0), IntMod(0), true, true , false, false}, // 1
{1, IntMod(3), IntMod(1), IntMod(0), IntMod(0), true, false, false, false}, // 2
{1, IntMod(4), IntMod(1), IntMod(1), IntMod(0), true, false, true , false}, // 3
{1, IntMod(5), IntMod(1), IntMod(1), IntMod(0), true, false, false, false}, // 4
{1, IntMod(6), IntMod(1), IntMod(1), IntMod(0), true, false, false, false}, // 5
{1, IntMod(7), IntMod(1), IntMod(1), IntMod(0), true, false, false, false}, // 6
{1, IntMod(8), IntMod(1), IntMod(1), IntMod(0), true, false, false, false}, // 7
{1, IntMod(9), IntMod(1), IntMod(1), IntMod(0), true, false, false, false}, // 8
{1, IntMod(10),IntMod(1), IntMod(1), IntMod(0), true, false, false, false} // 9
};
char getChar(FILE *fin) {
char ch = fgetc(fin);
while(!isdigit(ch))
ch = fgetc(fin);
return ch;
}
int main() {
int N, Q;
goodcnt[0] = 1;
for(int i = 1; i <= MAX_N; ++i)
goodcnt[i] = goodcnt[i - 1] * 10 - goodcnt[i - 2];
scanf("%d%d", &N, &Q);
for(int i = 1; i <= N; ++i)
update(i, updDigit[getChar(stdin) - '0']);
printf("%d\n", query(1, N).cntgood.val);
for(int i = 0; i < Q; ++i) {
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
if(t == 2)
update(x, updDigit[y]);
else
printf("%d\n", query(x, y).cntgood.val);
}
return 0;
}
