給定兩個字串 $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$。