P15073 [ICPC 2024 Chengdu R] Athlete Welcome Ceremony

Chengdu is about to host the 2025 World Games. During the athlete welcome ceremony at the opening event, there will be $n$ volunteers dressed in one of three different types of traditional folk costumes, lined up to welcome the athletes. These costumes are denoted by type $\texttt{a}$, $\texttt{b}$, and $\texttt{c}$. The positions of the volunteers have been determined, and now we need to assign costumes to the volunteers. To achieve a specific visual effect, adjacent volunteers must not wear the same type of costume. Among the $n$ volunteers, some already have one of the three types of folk costumes, while others do not have any and require custom-made costumes provided by the organizers. There are $Q$ custom-making plans, each specifying: making $x$ sets of costumes $\texttt{a}$, $y$ sets of costumes $\texttt{b}$, and $z$ sets of costumes $\texttt{c}$. For each custom-making plan, determine how many different valid costume arrangements can be made after distributing the custom-made costumes to the volunteers who do not have any costumes. Specifically, determine the number of ways for assigning costumes $\texttt{a}$, $\texttt{b}$ and $\texttt{c}$ under the condition of not exceeding the limits of the given plan. If two arrangements differ in the type of costume assigned to the same volunteer, they are considered different. Note that the same type of costumes are not distinguished from each other. As the number may be very large, please output the answer modulo $10^9+7$.

The first line contains two integers $n$ ($1\le n\le 300$) and $Q$ ($1\le Q\le 10^5$), representing the number of volunteers and the number of custom-making plans, respectively. The second line is a string $s$ of length $n$. It is guaranteed that the string $s$ contains only the characters $\texttt{a}$, $\texttt{b}$, $\texttt{c}$, and $\texttt{?}$. If the $i$-th character is one of $\texttt{a}$, $\texttt{b}$, and $\texttt{c}$, it indicates that the $i$-th volunteer already has the corresponding costume; otherwise, if it is $\texttt{?}$, it indicates that the $i$-th volunteer does not have any costume. Each of the next $Q$ lines contains three integers $x, y, z$ ($0 \le x, y, z \le 300$), representing a custom-making plan. It is guaranteed that the sum $x+y+z$ is no less than the number of volunteers without costumes.

Output $Q$ lines, with the $i$-th line containing an integer that represents the number of valid costume arrangements that satisfy the requirements for the $i$-th custom-making plan. Please output the answer modulo $10^9+7$.

In the first sample, the valid costume arrangements for the first custom-making plan are $\texttt{acbabc}$, $\texttt{acbcac}$, and $\texttt{acbcbc}$.