#CS1731. 单词组合

单词组合

题目背景

翻译自 CSES-1731 题。

题目描述

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

输入格式

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

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

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

输出格式

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

样例

ababc
4
ab
abab
c
cb

2

样例1解释 可以拼接出字符串 ababc 的两种方式：

• ab+ab+cab + ab + cab+ab+c

• abab+cabab + cabab+c

说明/提示

$1 \leq n \leq 50$

$1 \leq k \leq10^5$

所有单词的总长度不超过 10610^6 106。