Dane są dwa ciągi znaków $S$ oraz $T$.

Niech $S_{l,r}$ oznacza podciąg znaków $S$ od pozycji $l$ do $r$ włącznie.

Podciągiem $S_{l,r}$ nazywamy dowolny ciąg $S_{x,y}$ spełniający warunek $l \leq x \leq y \leq r$.

Niech $f(l,r)$ oznacza sumę liczby wystąpień wszystkich podciągów $S_{l,r}$ w ciągu $T$.

Należy obliczyć wartość poniższego wyrażenia:

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

Wynik należy podać modulo $(10^9+7)$.

Wejście

Dane wczytywane są ze standardowego wejścia.

Wejście składa się z dwóch linii, z których każda zawiera ciąg znaków składający się wyłącznie z małych liter alfabetu łacińskiego, reprezentujących odpowiednio $S$ oraz $T$.

Wyjście

Wynik należy wypisać na standardowe wyjście.

Wypisz jedną liczbę całkowitą będącą wynikiem obliczenia wyrażenia z treści zadania modulo $(10^9+7)$.

Przykład

Przykład 1

Wejście

aba
ba

Wyjście

59

Przykład 2

Wejście

ababc
babac

Wyjście

1094

Przykład 3

Wejście

aaaaa
aa

Wyjście

1008

Przykład 4

Wejście

arknights
genshinimpact

Wyjście

5901

Podzadania

Niech $\max(|S|,|T|)=n$.

• Podzadanie 1 (10 punktów): $1 \leq n \leq 60$.
• Podzadanie 2 (20 punktów): $1 \leq n \leq 300$.
• Podzadanie 3 (30 punktów): $1 \leq n \leq 2\,000$.
• Podzadanie 4 (25 punktów): $1 \leq n \leq 20\,000$.
• Podzadanie 5 (15 punktów): $1 \leq n \leq 500\,000$.