У Васи было три строки \(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\).