A. Подстрока и подпоследовательность
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Как-то раз Поликарп раздобыл две непустые строки s и t, состоящие из строчных букв латинского алфавита. Поликарп неплохо разбирается в строках, поэтому он сразу задался вопросом: сколько существует различных пар «x y» таких, что x — подстрока строки s, y — подпоследовательность строки t, а содержимое x и y одинаково. Две пары считаются различными, если в них различаются подстроки строки s или различаются подпоследовательности строки t. Прочтите условие до конца для точного понимания различности подстрок и подпоследовательностей в данной задаче.

Длиной строки s называется количество символов в ней. Пусть длина строки s обозначается |s|, тогда можно записать строку s в виде s = s1s2... s|s|.

Непустую строку x = s[a... b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|) будем называть подстрокой строки s. Например, «code» и «force» — подстроки «codeforces», а «coders» — нет. Две подстроки s[a... b] и s[c... d] считаются различными, если a ≠ c или b ≠ d. Например, если scodeforces», то s[2...2] и s[6...6] — различны, несмотря на то, что их содержимое одинаково.

Непустую строку y = s[p1p2... p|y|] = sp1sp2... sp|y| (1 ≤ p1 < p2 < ... < p|y| ≤ |s|) будем называть подпоследовательностью строки s. Например, «coders» — подпоследовательность «codeforces». Две подпоследовательности u = s[p1p2... p|u|] и v = s[q1q2... q|v|] считаются различными, если различны последовательности p и q.

Входные данные

Входные данные состоят из двух строк. Первая из них содержит s (1 ≤ |s| ≤ 5000), а вторая — t (1 ≤ |t| ≤ 5000). Обе строки состоят из строчных латинских букв.

Выходные данные

Выведите единственное число — количество различных пар «x y» таких, что x — подстрока строки s, y — подпоследовательность строки t, а содержимое x и y одинаково. Так как ответ может быть достаточно большим, выведите его остаток при делении на 1000000007 (109 + 7).

Примеры
Входные данные
aa
aa
Выходные данные
5
Входные данные
codeforces
forceofcode
Выходные данные
60
Примечание

Выпишем все пары «x y», которые входят в ответ в первом тестовом примере: «s[1...1] t[1]», «s[2...2] t[1]», «s[1...1] t[2]», «s[2...2] t[2]», «s[1...2] t[1 2]».