Даны две строки $S$ и $T$.

Обозначим через $S_{l,r}$ подстроку строки $S$, состоящую из символов с $l$-го по $r$-й включительно.

Подстрокой $S_{l,r}$ называется любая строка $S_{x,y}$, где $l \leq x \leq y \leq r$.

Пусть $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

Вывод:

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