自动人偶

Problem Description

某科学家制作了 $n$ 个机器人，将他们依次编号为 $1 \sim n$，并放置在可抽象为一数轴的某地上。其中，第 $i$ 个机器人被放置在数轴的坐标 $i$ 所对应的位置。 该科学家制作的机器人可执行两种移动指令：L 和 R。

• 当执行 L 指令时，机器人将沿数轴负方向移动一个单位长度。特别地，数轴的位置 $1$ 左侧有一座峭壁，如果机器人在坐标 $1$ 处执行 L 指令，则其由于被阻挡而无法完成移动，而停留在原地。
• 当执行 R 指令时，机器人将沿数轴正方向移动一个单位长度。特别地，数轴的位置 $n$ 右侧有一座悬崖，如果机器人在坐标 $n$ 处执行 R 指令，则其将从悬崖上坠落，并被损坏。
• 特别地，机器人中内置了自毁程序。若在执行完某条指令之后，其之前执行的指令序列中出现了自毁指令（某已知字符串 $S$）作为子串，则该机器人将立即爆毁，并被损坏。 现该科学家从所有长度为 $m$ 的指令序列中等概率随机地选取了一个序列 $T$，将其烧录至所有机器人的指令芯片中。这些机器人将依次执行 $T$ 中的所有指令。每当执行完毕所有指令，则回到 $T$ 的开头，从第一条指令开始重新执行，直至机器人由于坠落或爆毁而损坏。 请你计算，在充分长的时间之后，期望会剩下多少台没有损坏的机器人。换言之，期望下有多少台机器人可以执行任意多条指令而不被损坏。为避免精度误差，答案对 $10^9 + 7$ 取模。

Input

第一行一个整数 $t$ $(1 \leq t \leq 10)$，表示测试数据的组数。 对于每组数据： 第一行两个整数 $n$，$m$ $(1 \leq n \leq 30, 1 \leq m \leq 40)$ -- 机器人的个数，以及指令序列的长度。 接下来一行一个仅包含字符 L 和 R 的字符串 $S$ $(1 \leq |S| \leq 30)$ -- 机器人的自毁指令。

Output

对于每组数据输出一行一个整数，表明所求的答案。

Sample Input

2
3 2
LR
6 15
LRLRL

Sample Output

750000006
433410649

Source

2024“钉耙编程”中国大学生算法设计超级联赛（7）