Problem Description

Alice and Bob have recently become keen on playing a game called the “Brick Mini Contest”.

Initially, Alice and Bob each have $n$ bricks arranged in a row from left to right, and each brick is labeled with a lowercase English letter.

Alice may discard any number of bricks from her own row (she may also discard none). Bob may discard a consecutive segment of bricks from the left end and a consecutive segment of bricks from the right end (he may discard from only one side, or discard none from both sides). Neither of them is allowed to discard all of their bricks. Then Alice and Bob will each re-form their remaining bricks into a row, keeping the original order.

Alice and Bob are busy playing, so they ask you to compute how many different situations result in their final remaining rows being identical.

Two rows of bricks are identical if and only if they have the same number of bricks and the letter at each position is the same.

Two situations are different if and only if the remaining bricks of Alice (or Bob) are different between the two situations.

Input Format

The first line contains a positive integer $n$, the number of bricks.

The second line contains a lowercase string $s$ of length $n$, representing Alice’s initial row of bricks. The $i$-th character $s_i$ is the letter on the $i$-th brick.

The third line contains a lowercase string $t$ of length $n$, representing Bob’s initial row of bricks. The $i$-th character $t_i$ is the letter on the $i$-th brick.

Output Format

Output one line containing a non-negative integer, the answer.

5
bcabc
bbcca

9

20
egebejbhcfabgegjgiig
edfbhhighajibcgfecef

34

Hint

For all test points: $1\le n \le 3000$, and $s$ and $t$ contain only lowercase English letters.

Test point $1$ satisfies: $n\le3000$, and $s$ and $t$ each contain only one kind of letter.

Test points $2,3,4$ satisfy: $n\le100$.

Test points $5,6,7$ satisfy: $n\le500$.

Test points $8,9,10$ satisfy: $n\le3000$.

Thanks to w33z8kqrqk8zzzx33 for providing the testdata.

Translated by ChatGPT 5