题目描述

给定一个目标字符串和若干个字符串块（tile），你需要按照下面的规则使用这些 tile 覆盖整个目标串：

1. 一个 tile 只有在与目标串的某个子串完全相同时，才能覆盖这个子串；
2. 目标串的每个字符都必须至少被一个 tile 覆盖；
3. 每种 tile 可以使用任意多次，也不要求所有 tile 都被使用；
4. 第一个 tile 必须恰好覆盖目标串的开头，最后一个 tile 必须恰好覆盖目标串的结尾；
5. 每对相邻使用的 tile 必须至少重叠一个字符；
6. 对于相邻的前后两个 tile，后一个 tile 的起始位置必须严格大于前一个 tile 的起始位置，并且后一个 tile 的结束位置也必须严格大于前一个 tile 的结束位置。

原题给出的合法/非法覆盖方式示意如下：

Cover the String 原题示意图

请计算一共有多少种不同的覆盖方式。由于答案可能很大，只需输出对 $1000000007$ 取模后的结果。

输入格式

第一行一个整数 $t$：

表示测试数据组数。

对于每组数据：

1. 第一行是目标字符串 $S$，只包含大写英文字母，非空且长度不超过 1000；
2. 第二行一个正整数 $n$，表示 tile 的种类数，$n\le200$；
3. 接下来 $n$ 行，每行一个 tile。每个 tile 非空、长度不超过 200，也只包含大写英文字母。

不同测试数据之间有一个空行。

不同编号的 tile 即使字符串内容完全相同，也被视为不同种类。

输出格式

对于每组数据，输出一行一个整数，表示覆盖方案数对

取模后的结果。

样例输入

3
ABABA
1
ABA

AA
2
AA
AA

AA
1
BB

样例输出

1
2
0