描述

L国的仪仗队要穿越首都广场了。首都广场可以看做是一块N*M的矩形网格,仪仗队要从左上角的格点(0,0)行进到右下角的格点(N,M),行进过程中只能向右走或者向下走。如果把向右走记为’R’,把向下走记为’D’,则仪仗队的行进序列是一个包含M个’R’和N个’D’的字符串。
这时,L国的首长又提出了一个奇葩的要求。他认为仪仗队行走的序列中必须包含他给出的两个字符串。请你计算一下,满足首长要求的行进序列有多少种呢?

输入格式

第一行一个整数T,表示数据组数。
每组数据的第一行是两个整数M、N,表示行进序列由M个’R’和N个’D’构成。
每组数据的第二行和第三行是两个不相同的字符串,表示首长要求这两个字符串是行进序列的子串。

输出格式

一个整数,表示满足要求的行进序列的数量模1000000007的值。

样例输入

2
3 2
RRD
DDR
3 2
R
D

样例输出

1
10

数据范围与约定

  • 对于50% 的数据,1<=N,M<=50,字符串长度<=50,T=1。
  • 对于100% 的数据,1<=N,M<=100,字符串由’R’、’D’组成且长度<=100,1<=T<=10。