密码 - 题目

出于安全考虑，Yandex 的每位员工都需要定期更改其 @yandex-team.ru 邮箱的密码。

Yasha 有一套独特的密码更改流程。

在他入职 Yandex 的第一天，他选择了长度为 $M$ 的、字典序最小的可打印非空白 ASCII 字符序列作为密码。此后，他的每一个新密码都是之前尚未被 Yasha 使用过的、长度为 $M$ 的字典序最小的可打印非空白 ASCII 字符序列。

Yasha 在 Yandex 工作了很长时间，他开始担心很快就会用尽这类序列，因此决定在未来改变他的密码选择策略。

截至目前，Yasha 的当前密码是 $T$。

对于他的新密码，Yasha 想出了一个长度为 $N$ 的可打印非空白 ASCII 字符序列 $S$。这个新密码不受 $T$ 的任何限制：它可以比 $T$ 短、长，甚至与 $T$ 完全相同。现在，Yasha 想要估算 $S$ 与他所有过往密码之间的总相似度。

$S$ 与过去某个密码 $P$ 的相似度等于 $S$ 和 $P$ 的最长公共子串的长度。$S$ 与从字典序最小的密码开始直到当前密码的所有密码的组合相似度，等于 $S$ 与这些密码中每一个的相似度之和，结果对 $10^9 + 7$ 取模。

你的任务是帮助 Yasha 计算这个组合相似度。

输入包含两行。

第一行包含 Yasha 的未来密码 $S$，长度为 $N$ ($1 \le N \le 100$)。

第二行包含 Yasha 的当前密码 $T$，长度为 $M$ ($1 \le M \le 70$)。

每个序列完全由可打印的非空白 ASCII 字符组成，字符编码范围为 33 到 126（含）。

输出一个整数，即该问题的答案。

xyz
bb

QOJ.ac