#include <bits/stdc++.h> using namespace std; #define sz(x) (int)x.size() #define all(x) x.begin() , x.end() const int N = 131072; const int mod = 1e9 + 7; inline void ckadd(int &a , int b){ a += b; if(a >= mod)a -= mod; } struct Matrix{ vector<vector<int>>mat; Matrix():mat(11,vector<int>(11,0)){} friend Matrix mult(Matrix &a , Matrix &b){ Matrix c; for(int i = 0;i<11;i++){ for(int j = 0;j<11;j++){ for(int k = 0;k<11;k++){ ckadd(c.mat[i][j] , 1LL * a.mat[i][k] * b.mat[k][j] % mod); } } } return c; } void print(){ for(int i = 0;i<11;i++){ for(int j = 0;j<11;j++){ cout << mat[i][j] << " "; } cout << endl; } cout << endl; } } iden; vector < Matrix > t; Matrix merge(Matrix &x , Matrix &y){ return mult(x,y); } void init(){ t.assign(2*N , iden); } void update(int p, Matrix value) { // set value at position p for (t[p += N] = value; p > 1; p >>= 1){ t[p>>1] = merge(t[p] , t[p^1]); } } Matrix query(int l, int r) { // sum on interval [l, r] Matrix res = iden; queue<Matrix>v1; stack<Matrix>v2; for (r+=1 , l += N, r += N; l < r; l >>= 1, r >>= 1) { if (l&1) v1.push(t[l++]); if (r&1) v2.push(t[--r]); } while(!v1.empty()){ res = mult(res , v1.front()); v1.pop(); } while(!v2.empty()){ res = mult(res , v2.top()); v2.pop(); } return res; } // vector<Matrix>tree(4*N+7); // void update(int qp , Matrix &qv , int ind=1 , int l=0 , int r=N-1){ // if(l == r){ // tree[ind] = qv; // return; // } // int mid = (l + r) / 2; // if(qp <= mid)update(qp , qv , ind*2 , l , mid); // else update(qp , qv , ind*2+1 , mid+1 , r); // tree[ind] = mult(tree[ind*2] , tree[ind*2+1]); // } // Matrix query(int ql , int qr , int ind=1 , int l=0 , int r=N-1){ // if(l >= ql and r <= qr){ // cout << "carp : " << endl; // tree[ind].print(); // return tree[ind]; // } // else if(l > qr or r < ql)return iden; // int mid = (l + r) / 2; // Matrix A = query(ql,qr,ind*2,l,mid); // Matrix B = query(ql,qr,ind*2+1,mid+1,r); // return mult(A,B); // } void solve(){ for(int i = 0;i<11;i++){ iden.mat[i][i] = 1; } init(); int n,q; cin >> n >> q; string str; cin >> str; auto upd = [&](int p , int x){// p yi x yap Matrix tran; if(x == 3 and p > 0 and str[p-1] == '1'){ for(int i = 0;i<10;i++) for(int j = 0;j<10;j++) tran.mat[i][j] = 1; tran.mat[1][3] = 0; for(int i = 0;i<x;i++){ tran.mat[10][i] = 1; } } else if(p > 0 and str[p-1] == '1'){ for(int i = 0;i<10;i++) for(int j = 0;j<10;j++) tran.mat[i][j] = 1; tran.mat[1][3] = 0; for(int i = 0;i<x;i++){ tran.mat[10][i] = 1; } tran.mat[10][3] = 0; tran.mat[10][10] = 1; } else{ for(int i = 0;i<10;i++) for(int j = 0;j<10;j++) tran.mat[i][j] = 1; tran.mat[1][3] = 0; for(int i = 0;i<x;i++){ tran.mat[10][i] = 1; } tran.mat[10][10] = 1; } update(p , tran); }; auto que = [&](int l , int r){ Matrix st; for(int i = 0;i<str[l] - '0';i++)st.mat[0][i] = 1; st.mat[0][10] = 1; Matrix res = l == r ? iden : query(l+1 , r); st = mult(st , res); int ans = 0; for(int i = 0;i<=10;i++){ ckadd(ans , st.mat[0][i]); } return ans; }; for(int i = 0;i<n;i++){ upd(i , str[i] - '0'); } cout << que(0,n-1) << endl; while(q--){ int typ; cin >> typ; if(typ == 1){ int l,r; cin >> l >> r; l-- , r--; cout << que(l,r) << endl; } else{ int p,x; cin >> p >> x; p--; upd(p , x); str[p] = '0' + x; } } } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int testcase=1;//cin >> testcase; while(testcase--)solve(); cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl; }