给定两个字符串 $S$ 和 $T$。
记 $S_{l,r}$ 表示 $S$ 的第 $l$ 到第 $r$ 个字符组成的字符串。
定义 $S_{l,r}$ 的子串为任意满足 $l \leq x \leq y \leq r$ 的 $S_{x,y}$。
设 $f(l,r)$ 表示 $S_{l,r}$ 的所有子串在 $T$ 中出现次数的和。
则你需要计算：
$$\sum_{i=1}^{|S|} \sum_{j=i}^{|S|} f(i,j) \cdot(j-i+1)^2$$
对 $(10^9+7)$取模的结果。
输入格式
从标准输入中读入数据。
输入两行，每行分别读取一个仅包含小写字母的字符串，分别表示 $S$ 和 $T$。
输出格式
输出到标准输出。
输出一行一个整数，表示题目描述中的式子对 $(10^9+7)$ 取模的结果。
样例数据
样例 1 输入
aba
ba样例 1 输出
59样例 2 输入
ababc
babac样例 2 输出
1094样例 3 输入
aaaaa
aa样例 3 输出
1008样例 4 输入
arknights
genshinimpact样例 4 输出
5901子任务
设 $\max(|S|,|T|)=n$。
- 子任务 1（10分）： $1 \leq n \leq 60$。
- 子任务 2（20分）： $1 \leq n \leq 300$。
- 子任务 3（30分）： $1 \leq n \leq 2\,000$。
- 子任务 4（25分）： $1 \leq n \leq 20\,000$。
- 子任务 5（15分）： $1 \leq n \leq 500\,000$。