*由于公式敲得太累，以下所有的递推公式忽略取模，在实际的代码中请自行加上 考虑动态规划： $令dp[i][j][k][p=0/1/2]代表考虑字符串的前i个字符，当使用j个a,k个b,且最后一个字符是p+'a'的合法串个数$ 考虑字符串的第一个字符$s[1]$，进行初始化：

$$\begin{cases} dp[1][0][0][0]=1, & s[1]='a' \\ dp[1][0][0][1]=1, & s[1]='b' \\ dp[1][0][0][2]=1, & s[1]='c' \\ dp[1][1][0][0]=1,dp[1][0][1][1]=1,dp[1][0][0][2]=1, &s[1]='?' \end{cases} $$

状态转移： 若$s[i]!='?'，有考虑到相邻两个字符不相同，因此有$

$$\begin{cases}dp[i][j][k][0] = dp[i-1][j][k][1] + dp[i-1][j][k][2], & s[i]='a' \\dp[i][j][k][1] = dp[i-1][j][k][0] + dp[i-1][j][k][2], & s[i]='b' \\dp[i][j][k][2] = dp[i-1][j][k][0] + dp[i-1][j][k][1], & s[i]='c'\end{cases} $$

若$s[i]='?'，则有$

$dp[i][j][k][0] = dp[i-1][j-1][k][1] + dp[i-1][j-1][k][2]$ $dp[i][j][k][1] = dp[i-1][j][k-1][0] + dp[i-1][j][k-1][2]$ $dp[i][j][k][2] = dp[i-1][j][k][0] + dp[i-1][j][k][1]$

由于字符串是唯一确定的，假设字符串的前$i$位置恰有$cnt$个问号， $则dp[i][j][k][p]代表对于字符串前i位，使用了j个a,k个b,cnt-j-k个c，末尾是p的方案数$ 因此，对于某个查询${x,y,z}$ 有方案数$f[x][y][z]=sum(dp[n][j][k][p])$, $for$ $all$ $j ≤ x, k ≤ y, cnt[n] - j - k ≤ z, p ∈ {0, 1, 2})$ 其中$cnt[n]$代表字符串总的问号个数 对于上述求和，可以使用三维前缀和进行维护。 示例代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=310;
#define int long long
const int mod=1e9+7;

int dp[N][N][N][3];
int f[N][N][N];
int cnt[N];

int n,m;
string s;

void solve()
{
	cin>>n>>m;
	cin>>s;
	s = ' '+s;
	for(int i=1;i<=n;i++)
	{
		cnt[i]=cnt[i-1];
		if(s[i]=='?') cnt[i]++;
	}
	if(s[1]=='?')
	{
		dp[1][1][0][0]=1;
		dp[1][0][1][1]=1;
		dp[1][0][0][2]=1;
	}
	else
		dp[1][0][0][s[1]-'a']=1;
		
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<=cnt[i];j++)
		{
			for(int k=0;j+k<=cnt[i];k++)
			{
				if(s[i]!='?')
				{
					int res=dp[i-1][j][k][0]+dp[i-1][j][k][1]+dp[i-1][j][k][2];
					dp[i][j][k][s[i]-'a']=(res-dp[i-1][j][k][s[i]-'a'])%mod;
					continue;
				}
				if(j!=0) dp[i][j][k][0]=(dp[i-1][j-1][k][1]+dp[i-1][j-1][k][2])%mod;
				if(k!=0) dp[i][j][k][1]=(dp[i-1][j][k-1][0]+dp[i-1][j][k-1][2])%mod;
				if(cnt[i]-j-k!=0)
						 dp[i][j][k][2]=(dp[i-1][j][k][0]+dp[i-1][j][k][1])%mod;				
			}
		}
	}
	
	for(int i=0;i<=cnt[n];i++)
		for(int j=0;i+j<=cnt[n];j++)
			f[i][j][cnt[n]-i-j]=(dp[n][i][j][0]+dp[n][i][j][1]+dp[n][i][j][2])%mod;
			
	for(int i=0;i<=300;i++)
		for(int j=0;j<=300;j++)
			for(int k=0;k<=300;k++)
			{
				if(i>0) f[i][j][k] += f[i-1][j][k];
				if(j>0) f[i][j][k] += f[i][j-1][k];
				if(k>0) f[i][j][k] += f[i][j][k-1];
				if (i&&j) f[i][j][k] += mod - f[i - 1][j - 1][k];
                if (k&&j) f[i][j][k] += mod - f[i][j - 1][k - 1];
                if (i&&k) f[i][j][k] += mod - f[i - 1][j][k - 1];
                if (i&&j&&k) f[i][j][k] += f[i - 1][j - 1][k - 1];
                f[i][j][k] %= mod;
			}
	
	while(m--)
	{
		int x,y,z; cin>>x>>y>>z;
		cout<<f[x][y][z]<<endl; 

	}
}

signed main()
{
	solve();
	return 0;
}