Problem K

/*
 _____ _             _              _           _
|_   _| |__   ___   / \   _ __  ___| |__  _   _| |
  | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  | | | | | |  __// ___ \| | | \__ \ | | | |_| | |
  |_| |_| |_|\___/_/   \_\_| |_|___/_| |_|\__,_|_|

*/
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<ll int,ll int>
#define msi         map<string,ll int>
#define mis         map<ll int, string>
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define mpi         map<pair<ll int,ll int>,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define vii         vector<pair<ll int, ll int>>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define what_is(x)  cerr << #x << " is " << x << endl;
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
using namespace std;
#define PI 3.141592653589793
#define N  100005
ll n,q;
vector<vector<ll>> a[N],seg[4*N];
bool  lazy[4*N];

vector<vector<ll>> rev(vector<vector<ll>> p1)
{
	vector<vector<ll>> p2(2,vector<ll>(2));
	rep(i,0,2)
	{
		rep(j,0,2)
		{
			p2[i][j]=p1[(!i)][(!j)];
		}
	}
	return p2;
}

vector<vector<ll>> prod(vector<vector<ll>> p1 ,vector<vector<ll>>  p2)
{
	vector<vector<ll>> p3(2,vector<ll>(2,0));
	rep(i,0,2)
	{
		rep(j,0,2)
		{
			rep(k,0,2)
			{
				p3[i][j]+=(p1[i][k]*p2[k][j])%hell;
				p3[i][j]%=hell;
			}
		}
	}
	return p3;
}

vi fun(ll x,ll y, vector<vector<ll>> p1)
{
	vi ans(2);
	ans[0]=((p1[0][0]*x)%hell+(p1[1][0]*y)%hell)%hell;
	ans[1]=((p1[0][1]*x)%hell+(p1[1][1]*y)%hell)%hell;
	return ans;
}

void build(ll cur,ll st,ll end)
{
	if(st==end)
	{
		seg[cur]=a[st];
		return;
	}
	ll mid=(st+end)>>1;
	build(2*cur,st,mid);
	build(2*cur+1,mid+1,end);
	seg[cur]=prod(seg[2*cur],seg[2*cur+1]);					/* 1-change */
}
void updaterange(ll cur,ll st,ll end,ll l,ll r)
{
	if(lazy[cur]!=0)                                    /* 2-change */
	{
		seg[cur]=rev(seg[cur]);					/* 3-change */
		if(st!=end)
		{
			lazy[2*cur]!=lazy[2*cur];						/* 4-change */
			lazy[2*cur+1]!=lazy[2*cur+1];                   /* 5-change */
		}
		lazy[cur]=0;                                    /* 6-change */
	}
	if(st>end||st>r||end<l) return;
	if(l<=st&&end<=r)
	{
		seg[cur]=rev(seg[cur]);					    /* 7-change */
		if(st!=end)
		{
			lazy[2*cur]!=lazy[2*cur];						/* 4-change */
			lazy[2*cur+1]!=lazy[2*cur+1];                   /* 5-change */
		}
		return;
	}
	ll mid=(st+end)>>1;
	updaterange(2*cur,st,mid,l,r);
	updaterange(2*cur+1,mid+1,end,l,r);
	seg[cur]=prod(seg[2*cur],seg[2*cur+1]);                  /* 10-change */
}
vector<vector<ll>> query(ll cur,ll st,ll end,ll l,ll r)
{
	if(st>end||st>r||end<l) return {{1,0},{0,1}};
	if(lazy[cur]!=0)                                    /* 2-change */
	{
		seg[cur]=rev(seg[cur]);					/* 3-change */
		if(st!=end)
		{
			lazy[2*cur]!=lazy[2*cur];						/* 4-change */
			lazy[2*cur+1]!=lazy[2*cur+1];                   /* 5-change */
		}
		lazy[cur]=0;                                    /* 6-change */
	}
	if(st>=l&&end<=r) return seg[cur];
	ll mid=(st+end)>>1;
	vector<vector<ll>> ans1=query(2*cur,st,mid,l,r);
	vector<vector<ll>> ans2=query(2*cur+1,mid+1,end,l,r);
	return prod(ans1,ans2);                                 /* 14-change */
}
void solve()
{
	//ll n,q;
	cin>>n>>q;
	string s;
	cin>>s;
	vector<vector<ll>> A(2,vector<ll>(2,1)),B(2,vector<ll>(2,1));
	A[0][1]=0;
	B[1][0]=0;
	rep(i,0,n)
	{
		if(s[i]=='A')
			a[i+1]=A;
		else
			a[i+1]=B;
	}
	build(1,1,n);
	rep(i,0,q)
	{
		ll type;
		cin>>type;
		if(type==1)
		{
			ll l,r;
			cin>>l>>r;
			updaterange(1,1,n,l,r);
		}
		else
		{
			ll l,r,x,y;
			cin>>l>>r>>x>>y;
			vi ans=fun(x,y,query(1,1,n,l,r));
			cout<<ans[0]<<" "<<ans[1]<<endl;
		}
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		solve();
	}
	time
	return 0;
}