P7334

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10,p=998244353,p2=p-1;
int n,Q,len,ans,a[maxn],id[maxn];
struct block
{
    int L,R,lz1,lz2;
}b[maxn];
void init()
{
    cin>>n>>Q;
    len=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        id[i]=(i-1)/len+1;
        b[id[i]].lz1=b[id[i]].lz2=0;
        if(i%len==1) b[id[i]].L=i;
        if(i%len==0) b[id[i]].R=i;
    }
    b[id[n]].R=n;
}
inline int power(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=(res*x)%p;
        x=(x*x)%p;
        y>>=1;
    }
    return res;
}
inline int power2(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=(res*x)%p2;
        x=(x*x)%p2;
        y>>=1;
    }
    return res;
}
inline void pushdown(int w)
{
    for(int i=b[w].L;i<=b[w].R;i++)
    {
        int x=b[w].lz1,y=b[w].lz2;
        while(x && a[i]>1)
        {
            a[i]=sqrt(a[i]);
            x--;
        }
        int z=power2(2,y);
        a[i]=power(a[i],z);
    }
    b[w].lz1=b[w].lz2=0;
}
void work1(int l,int r)
{
    if(id[l]==id[r])
    {
        pushdown(id[l]);
        for(int i=l;i<=r;i++) a[i]=sqrt(a[i]);
        return;
    }
    pushdown(id[l]);
    for(int i=l;i<=b[id[l]].R;i++) a[i]=sqrt(a[i]);
    for(int i=id[l]+1;i<=id[r]-1;i++)
    {
        if(b[i].lz2) b[i].lz2--;
        else b[i].lz1++;
    }
    pushdown(id[r]);
    for(int i=b[id[r]].L;i<=r;i++) a[i]=sqrt(a[i]);
}
void work2(int l,int r)
{
    if(id[l]==id[r])
    {
        pushdown(id[l]);
        for(int i=l;i<=r;i++) a[i]=(a[i]*a[i])%p;
        return;
    }
    pushdown(id[l]);
    for(int i=l;i<=b[id[l]].R;i++) a[i]=(a[i]*a[i])%p;
    for(int i=id[l]+1;i<=id[r]-1;i++) b[i].lz2++;
    pushdown(id[r]);
    for(int i=b[id[r]].L;i<=r;i++) a[i]=(a[i]*a[i])%p;
}
void answer()
{
    while(Q--)
    {
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1) work1(l,r);
        else work2(l,r);
    }
}
void output()
{
    for(int i=1;i<=n;i++)
    {
        int x=b[id[i]].lz1,y=b[id[i]].lz2;
        while(x && a[i]>1)
        {
            a[i]=sqrt(a[i]);
            x--;
        }
        if(a[i]==1)
        {
            ans=(ans+1)%p;
            continue;
        }
        int z=power2(2,y);
        a[i]=power(a[i],z);
        ans=(ans+a[i])%p;
    }
    cout<<ans;
}
signed main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    init();
    answer();
    output();
    return 0;
}