小莫的计数(简单版本)
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小莫想要创造一个仅由MONIKA六个大写字符构成的长度为n的字符串，但是这个字符串有m个限制，每个限制包含两个字符a,b，代表字符串中字符b的前面一个字符一定不能是a，求满足条件的字符串的数量，因为字符串的数量可能很大，所以请将答案对1e9+7取模。

输入描述:

第一行包含一个整数T代表数据组的个数。

每组数据的第一行包含两个整数n,m，代表字符串的长度和限制的个数，接下来m行每行有俩个字符，并且保证字符串中只会出现M,O,N,I,K,A六个大写字母。

1\leqq T \leqq 1e4

注意在简单版本中所有组的n之和 \leqq 1e5

0 \leqq m \leqq 36

输出描述:

对于每组数据输出一个值代表字符串的种类
示例1

输入

复制 
1
2 1
M O

输出

复制 
35
示例2

输入

复制 
1
100000 3
M O
K A
N I

输出

复制 
757032540