Matching Block Sequences

Alice and Bob are playing a game called "Block Race". Initially, each of them has n blocks arranged in a row from left to right. Each block is marked with a lowercase English letter.

Alice is allowed to discard any number of blocks (possibly none) from her row, but she cannot discard all of them. In other words, she chooses a non‐empty subsequence of her blocks (keeping their original order).

Bob, on the other hand, is allowed to discard a contiguous segment from the beginning and a contiguous segment from the end of his row (either one or both segments can be empty), but he also must keep at least one block. Equivalently, Bob selects a non‐empty contiguous subsequence of his blocks.

After discarding, both Alice and Bob line up their remaining blocks in the same order as originally. We say the two resulting sequences of blocks are identical if they have the same length and the letter in each corresponding position is the same.

Your task is to help them calculate the total number of different pairs of choices (one for Alice and one for Bob) so that the remaining sequences are identical. Two pairs of choices are considered different if Alice’s choice in one pair is different from her choice in the other, or Bob’s choice is different.

The answer can be huge so output the exact integer value.

Note: In this problem, a subsequence of a string is obtained by deleting some (possibly zero) characters without changing the order of the remaining characters, while a contiguous subsequence is obtained by choosing a segment from the string.

Also, any formula in the statement is rendered in \(\LaTeX\) format. For example, the condition that Alice and Bob each have \(n\) blocks is represented as \(n\).

inputFormat

The input consists of three lines:

1. An integer \(n\) (the number of blocks each person has).
2. A string of length \(n\) representing Alice’s blocks (from left to right).
3. A string of length \(n\) representing Bob’s blocks (from left to right).

It is guaranteed that \(n \ge 1\) and both strings consist only of lowercase English letters.

outputFormat

Output a single integer — the total number of pairs of choices (one subsequence for Alice and one contiguous subsequence for Bob) such that the two resulting block sequences are identical.

sample

3
abc
abc

6