字符串的拼接 描述 给出一个长度为 n 的字符串和 k 个不同的单词。请计算通过单词拼接得到这个字符串的方案种数（对 109+7 取余的结果）。 输入 第一行包含一个长度为 n 的字符串，且仅由小写

字符串的拼接

描述

给出一个长度为 n 的字符串和 k 个不同的单词。请计算通过单词拼接得到这个字符串的方案种数（对 10⁹+7 取余的结果）。tla100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入

第一行包含一个长度为 n 的字符串，且仅由小写字母 a-z 组成。tla100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第二行包含一个整数 k：表示可用的单词个数。tla100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
接下去 k 行，每行一个单词。保证没有相同单词，且所有单词也仅包含小写字母 a-z。tla100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
tla100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1<=n<=5000;tla100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1<=k<=10⁵;tla100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
所有单词的总长度不超过 10⁶;

输出

方案个数对 10⁹+7 取余的结果。

样例输入

ababc
4
ab
abab
c
cb

样例输出

2

提示

【样例说明】tla100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
可能的拼接有 2 种：ab+ab+c 和 abab+c。