链接: https://cses.fi/problemset/task/1731

板块: String Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个长度为 $n$ 的字符串，以及一个包含 $k$ 个单词的词典。你有多少种方式可以用这些单词拼出该字符串？

输入

第一行输入包含一个由 a–z 之间 $n$ 个字符组成的字符串。

第二行包含一个整数 $k$：词典中单词的个数。

最后有 $k$ 行描述这些单词。每个单词都是唯一的，且由 a–z 的字符组成。

输出

输出方式数，对 $10^9+7$ 取模。

数据范围

$1 \le n \le 5000$ $1 \le k \le 10^5$ 单词的总长度至多为 $10^6$

样例输入

ababc
4
ab
abab
c
cb

样例输出

2