У Васи было три строки \(a\), \(b\) и \(s\), состоящие из строчных символов латинского алфавита. Длины строк \(a\) и \(b\) равны \(n\), длина строки \(s\) равна \(m\).
Вася решил выбрать подстроку из строки \(a\), затем выбрать подстроку из строки \(b\) и сконцентрировать их. Формально, он выбирает подотрезок \([l_1, r_1]\) (\(1 \leq l_1 \leq r_1 \leq n\)) и подотрезок \([l_2, r_2]\) (\(1 \leq l_2 \leq r_2 \leq n\)), а после конкатенации получает строку \(a[l_1, r_1] + b[l_2, r_2] = a_{l_1} a_{l_1 + 1} \ldots a_{r_1} b_{l_2} b_{l_2 + 1} \ldots b_{r_2}\).
Теперь Васю заинтересовал вопрос, сколькими способами он может выбрать пару отрезков так, что выполнены следующие условия:
- отрезки \([l_1, r_1]\) и \([l_2, r_2]\) пересекаются, то есть существует хотя бы одно целое число \(x\), такое что \(l_1 \leq x \leq r_1\) и \(l_2 \leq x \leq r_2\);
- полученная Васей в итоге строка \(a[l_1, r_1] + b[l_2, r_2]\) равна строке \(s\).
Выходные данные
Выведите одно целое число — количество способов выбрать пару отрезков, удовлетворяющую Васиным условиям.
Примечание
Перечислим все пары отрезков, которые мог выбрать Вася в первом примере:
- \([2, 2]\) и \([2, 5]\);
- \([1, 2]\) и \([2, 4]\);
- \([5, 5]\) и \([2, 5]\);
- \([5, 6]\) и \([3, 5]\);
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 5
aabbaa
baaaab
aaaaa
|
4
|
|
2
|
5 4
azaza
zazaz
azaz
|
11
|
|
3
|
9 12
abcabcabc
xyzxyzxyz
abcabcayzxyz
|
2
|