2つの文字列 $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$ に出現する回数の総和とする。

このとき、以下の式を $(10^9+7)$ で割った余りを計算せよ。

$$\sum_{i=1}^{|S|} \sum_{j=i}^{|S|} f(i,j) \cdot(j-i+1)^2$$

入力

標準入力からデータを読み込む。

入力は2行からなり、各行に小文字のみからなる文字列 $S$ と $T$ がそれぞれ与えられる。

出力

標準出力に出力する。

問題文中の式の値を $(10^9+7)$ で割った余りを1行で出力せよ。

入出力例

入出力例 1

aba
ba

59

入出力例 2

ababc
babac

1094

入出力例 3

aaaaa
aa

1008

入出力例 4

arknights
genshinimpact

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$。