题目背景

翻译自 CSES-1731 题。

题目描述

给定一个长度为 $n$ 的字符串和一个包含 $k$ 个单词的字典。你需要计算用这些单词拼接出这个字符串的不同方法有多少种。

输入格式

第一行输入一个长度为 $n$ 的字符串，该字符串由小写字母组成（字符范围 $a–z$）。

第二行输入一个整数 $k$：字典中单词的数量。

接下来的 $k$ 行，每行描述一个单词。每个单词是唯一的，并且由小写字母组成。

输出格式

输出拼接成该字符串的方法数，结果对 $10^9+7$ 取模。

样例

ababc
4
ab
abab
c
cb

2

样例1解释

可以拼接出字符串 ababc 的两种方式：

• $ab + ab + c$
• $abab + c$

说明/提示

$1 \leq n \leq 5000$；

$1 \leq k \leq10^5$；

所有单词的总长度不超过 $10^6$。

友情提示

英文字母abcdefghijklnmopqrstuvwxyz共26个