Word Combinations

题目描述

给定一个长度为 n 的字符串和包含 k 个单词的字典。可以用这些单词以多少种方式构造出该字符串？

输入格式

第一行输入包含一个由字符 a–z 组成的长度为 n 的字符串。 第二行有一个整数 k：字典中的单词数。 接下来有 k 行描述这些单词。每个单词都是唯一的，并且由字符 a–z 组成。

输出格式

输出方法数对 $10^9+7$ 取模的结果。

ababc
4
ab
abab
c
cb

2

提示

$1 \le n \le 5000$ $1 \le k \le 10^5$ $10^6$ 样例解释：可能的方式是 ab+ab+c 和 abab+c。

标签: CSES1731|字符串

来源

CSES1731|字符串