给定两个字符串 $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$。