题目描述

成都即将主办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$行，每行包含一个整数，表示满足该定制方案要求的有效服装排列的数量。请输出对$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

样例解释

在第一个示例中，第一个定制方案的有效服装排列为acbabc、acbcac和acbcbc。