说明

成都即将举办 2025 年世界运动会。在开幕式运动员欢迎仪式上，将有 $n$ 名志愿者穿着三种不同类型的传统民俗服装，列队欢迎运动员。这些服装类型用 $\texttt{a}$、$\texttt{b}$ 和 $\texttt{c}$ 表示。志愿者的位置已经确定，现在我们需要为他们分配服装。为了实现特定的视觉效果，相邻的志愿者不能穿着相同类型的服装。

在这 $n$ 名志愿者中，一些人已经拥有三种民俗服装中的一种，而另一些人则没有任何服装，需要主办方提供定制服装。共有 $Q$ 个定制计划，每个计划指定：制作 $x$ 套 $\texttt{a}$ 型服装、$y$ 套 $\texttt{b}$ 型服装和 $z$ 套 $\texttt{c}$ 型服装。

对于每个定制计划，确定在将定制服装分发给没有服装的志愿者后，可以形成多少种不同的有效服装安排。具体来说，在不超过给定计划限制的条件下，计算分配 $\texttt{a}$、$\texttt{b}$ 和 $\texttt{c}$ 型服装的方案数。如果两种安排中同一名志愿者分配的服装类型不同，则视为不同的安排。注意，同一类型的服装彼此不作区分。由于数量可能非常大，请输出答案对 $10^9+7$ 取模的结果。

输入格式

• 第一行包含两个整数 $n$（$1\le n\le 300$）和 $Q$（$1\le Q\le 10^5$），分别表示志愿者人数和定制计划的数量。
• 第二行是一个长度为 $n$ 的字符串 $s$。保证字符串 $s$ 仅包含字符 $\texttt{a}$、$\texttt{b}$、$\texttt{c}$ 和 $\texttt{?}$。如果第 $i$ 个字符是 $\texttt{a}$、$\texttt{b}$、$\texttt{c}$ 之一，则表示第 $i$ 名志愿者已经拥有对应的服装；否则，如果是 $\texttt{?}$，则表示第 $i$ 名志愿者没有任何服装。
• 接下来的 $Q$ 行，每行包含三个整数 $x, y, z$（$0 \le x, y, z \le 300$），表示一个定制计划。保证 $x+y+z$ 不小于没有服装的志愿者人数。

输出格式

输出 $Q$ 行，第 $i$ 行包含一个整数，表示满足第 $i$ 个定制计划要求的有效服装安排数量。请输出答案对 $10^9+7$ 取模的结果。

6 3
a?b??c
2 2 2
1 1 1
1 0 2

3
1
1

6 3
??????
2 2 2
2 3 3
3 3 3

30
72
96

提示

在第一个样例中，第一个定制计划的有效服装安排是 $\texttt{acbabc}$、$\texttt{acbcac}$ 和 $\texttt{acbcbc}$。

翻译由 DeepSeek V3 完成