K. Addition Robot（矩阵+线段树）

int n,q;
char s[MAXN];
struct M
{
    ll m[2][2];
    M(){mem(m,0);}
}A,B;
M mul(M a, M b)
{
	M ans;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				ans.m[i][j] = (ans.m[i][j] + a.m[i][k] * b.m[k][j] % mod) % mod;
	return ans;
}
struct Segment_Tree
{
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    M c[MAXN<<2][2];
    int lazy[MAXN<<2];
    inline int ls(int p) {return p<<1;}
    inline int rs(int p) {return p<<1|1;}
    void push_up(int p) 
    {
        c[p][0]=mul(c[ls(p)][0],c[rs(p)][0]);
        c[p][1]=mul(c[ls(p)][1],c[rs(p)][1]);
    }
    void push_down(int p)
    {
        swap(c[ls(p)][0],c[ls(p)][1]);
        swap(c[rs(p)][0],c[rs(p)][1]);
        lazy[ls(p)]^=lazy[p];
        lazy[rs(p)]^=lazy[p];
        lazy[p]=0;
    }
    void build(int rt,int l,int r)
    {
        lazy[rt]=0;
        if(l==r)
        {
            if(s[l]=='A') c[rt][0]=A,c[rt][1]=B;
            else c[rt][0]=B,c[rt][1]=A;
            return;
        }
        int mid = (l+r)>>1;
        build(lson);build(rson);
        push_up(rt);
    }
    void Query(int ql,int qr,int rt,int l,int r,M & ans)
    {
        if(ql<=l && r<=qr)
        {
            ans=mul(ans,c[rt][0]);
            return;
        }
        if(lazy[rt]) push_down(rt);
        int mid=(l+r)>>1;
        if(ql<=mid) Query(ql,qr,lson,ans);
        if(qr>mid) Query(ql,qr,rson,ans);
        return ;
    }
    void update(int ql,int qr,int rt,int l,int r)//区间更新
    {
        if(ql<=l && qr>=r) {lazy[rt]^=1;swap(c[rt][0],c[rt][1]);return;}
        if(lazy[rt]) push_down(rt);
        int mid=(l+r)>>1;
        if(ql<=mid) update(ql,qr,lson);
        if(qr>mid) update(ql,qr,rson);
        push_up(rt);
    }
}tree;

int main()
{
    rd(n),rd(q);
    scanf("%s",s+1);
    A.m[0][0] = A.m[1][0] = A.m[1][1] = B.m[0][0] = B.m[0][1] = B.m[1][1] = 1;
    tree.build(1,1,n);
    while(q--)
    {
        int op;rd(op);
        if(op==1)
        {
            int l,r;rd(l),rd(r);
            tree.update(l,r,1,1,n);
        }
        else
        {
            int l,r,a,b;
            rd(l),rd(r),rd(a),rd(b);
            M ans,base;
            ans.m[0][0]=ans.m[1][1]=1;
            base.m[0][0]=a,base.m[0][1]=b;
            tree.Query(l,r,1,1,n,ans);
            base=mul(base,ans);
            printf("%lld %lld\n",base.m[0][0],base.m[0][1]);
        }
    }
    //stop;
    return 0;
}