侠之大者

时间限制：1000ms

空间限制：1024MB

题目背景

在春节档首日预售票房冠军，史诗巨作《射雕英雄传侠之大者》中，真正的侠之大者欧阳锋舞着黑色风火轮，独自在襄阳城外抵挡成吉思汗的入侵。 倘若不是（我最爱的）肖战哥哥饰演的郭靖从中作梗，恐怕成吉思汗早已被欧阳锋击毙。

打退欧阳锋之后，郭靖黄蓉二人在城门外面对千军万马，手拉着手，假模假式地劝退了来犯的蒙古大军，为襄阳城鞠躬尽瘁死而后已，实乃一段千古佳话（大嘘）。 而欧阳锋一人对抗千军万马的实力来源，正是那本由郭靖黄蓉伪作，颠鸾倒凤倒行逆施（什么形容词）的《九阴真经》。

九阴真经中，原本含有内功、招式、心法三类内容各若干节，顺序排布。为了让欧阳锋走火入魔，需要把其中的若干节进行替换，才能让这本伪作九阴真经狗屁不通却又暗藏玄机，颠三倒四而又粉饰太平（这又是什么形容词）。

题目描述

具体而言，原本的《九阴真经》可以视作一个仅包含字母 $abc$ 的字符串，字母 $a$ 代表一节内功，字母 $b$ 代表一节招式，字母 $c$ 代表一节心法。

现在，黄蓉从中删去了若干节，将删去的节记作字符?。现在，黄蓉手中还有自己杜撰的 $x$ 节内功， $y$ 节招式， $z$ 节心法，她需要用这些内容填补被删去的章节。（即，对于一个仅含字符 $a,b,c,?$ 的字符串，用字母 $a,b,c$ 替换字符 $?$ ，最多有 $x$ 个 $a$ ， $y$ 个 $b$ ， $z$ 个 $c$ 可供使用）

此外，为了保证能使欧阳锋走火入魔，相邻的两节不能是同一种内容。（即，字符串中连续的两个字符不能相同）。

请问以黄蓉手中现有的资源，有多少种方式能够编撰九阴真经？(题目保证数据合法，即至少有一种编撰方式)。 由于结果可能很大，请输出它在 $10^9+7$ 下取模的结果。

输入格式

第一行包含两个整数 $n,m$ ，表示字符串的长度和询问次数。 第二行包含一个字符串，表示需要填补内容的九阴真经。 接下来 $m$ 行，每行包含三个整数 $x,y,z$ ，表示可供填补的内功、招式、心法的数量。

输出格式

对于每个询问，输出一行，每行一个整数，表示编撰假《九阴真经》的方案数在$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

数据范围

对于 $60\%$ 的数据，保证 $m=1$

对于 $100\%$ 的数据，保证 $1\le n \le 300$ ， $0\le x,y,z \le300$ ， $1\le m\le 10^5$