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

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

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

Непустую строку y = s[p₁p₂... p_|y|] = s_p1s_p2... s_p|y| (1 ≤ p₁ < p₂ < ... < p_|y| ≤ |s|) будем называть подпоследовательностью строки s. Например, «coders» — подпоследовательность «codeforces». Две подпоследовательности u = s[p₁p₂... p_|u|] и v = s[q₁q₂... q_|v|] считаются различными, если различны последовательности p и q.