Надскладне завдання

Обмеження: 4 сек., 512 МіБ

Богданові дали надскладне завдання — написати умову до задачі для міжнародної студентської олімпіади. Таке почесне завдання йому доручили через неабиякі навички в написанні умов. Ці навички — це результат щоденної роботи над умовами.

Богдан знає, що для того щоб написати гарні умови потрібно лише трохи змінити минулорічні. Минулого року він вже писав дві такі умови. Ці умови можна записати як два рядки — \(s\) та \(t\). Богдан впевнений, що для того щоб написати гарну умову потрібно знати скільки однакових пар підрядків є в рядках \(s\) та \(t\). Звісно він міг би сам знайти це, але йому ж ніколи — олімпіада вже на носі. Допоможіть йому знайти скільки однакових пар підрядків є в рядках \(s\) та \(t\). Тобто, потрібно знайти кількість четвірок \(l_1\), \(r_1\), \(l_2\), \(r_2\), таких що \(r_1 - l_1 = r_2 - l_2\) і \(s[l_1 ... r_1] = t[l_2 ... r_2]\).

Підрядок — це непорожня зв’язна частина рядка. Тобто такий рядок, який можна отримати за допомогою видалення будь-якої кількості символів з початку та з кінця рядка.

Вхідні дані

У першому рядку задано один рядок \(s\).

У другому рядку задано один рядок \(t\).

Вихідні дані

В єдиному рядку виведіть кількість однакових підрядків рядків \(s\) та \(t\).

Обмеження

\(1 \le |s| \le 10^4\),

\(1 \le |t| \le 300\),

\(|s|\) — позначає довжину рядка,

рядки складаються лише із маленьких букв англійського алфавіту (a-z).

Оцінювання задачі складається із наступних блоків:

1 бал — приклад з умови,

4 бали — блок тестів у яких \(|s| \le 50\) і \(|t| \le 50\),

10 балів — блок тестів у яких \(|s| \le 300\) і \(|t| \le 300\),

10 балів — блок тестів у яких \(|s| \le 10^4\) і \(|t| \le 300\),

Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
aba aab	6

Примітки

В першому прикладі є одна спільна пара підрядків ab, одна пара підрядків b та 4 пари підрядків a.