Даны две строки $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$.