成都即将举办 2025 年世界运动会。在开幕式的运动员欢迎仪式上，将有 $n$ 名志愿者身着三种传统民俗服饰之一，排成一列欢迎运动员。这些服饰分别记为类型 a、b 和 c。志愿者的位置已经确定，现在我们需要为志愿者分配服饰。为了达到特定的视觉效果，相邻的志愿者不能穿着相同类型的服饰。

在 $n$ 名志愿者中，有些人已经拥有了三种民俗服饰中的一种，而另一些人则没有任何服饰，需要由主办方提供定制服饰。共有 $Q$ 个定制计划，每个计划指定：制作 $x$ 套 a 类服饰，$y$ 套 b 类服饰，以及 $z$ 套 c 类服饰。

对于每个定制计划，请确定在将定制服饰分发给没有服饰的志愿者后，有多少种不同的有效服饰排列方式。具体来说，确定在不超过给定计划限制的条件下，分配 a、b 和 c 类服饰的方法数。如果两种排列在同一名志愿者身上分配的服饰类型不同，则视为不同。注意，同类型的服饰之间不作区分。由于结果可能非常大，请输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 300$) 和 $Q$ ($1 \le Q \le 10^5$)，分别表示志愿者的人数和定制计划的数量。

第二行是一个长度为 $n$ 的字符串 $s$。保证字符串 $s$ 仅包含字符 a、b、c 和 ?。如果第 $i$ 个字符是 a、b 或 c 中的一个，则表示第 $i$ 名志愿者已经拥有相应的服饰；否则，如果字符为 ?，则表示第 $i$ 名志愿者没有任何服饰。

接下来的 $Q$ 行，每行包含三个整数 $x, y, z$ ($0 \le x, y, z \le 300$)，表示一个定制计划。保证 $x + y + z$ 的总和不小于没有服饰的志愿者人数。

输出格式

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

样例

样例输入 1

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

样例输出 1

3
1
1

样例输入 2

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

样例输出 2

30
72
96

说明

在第一个样例中，对于第一个定制计划，有效的服饰排列为 acbabc、acbcac 和 acbcbc。