Description

Find how many distinct common subsequences the $3$ character sequences share, excluding the empty sequence.

Input Format

The first line contains a positive integer $n$, denoting the length of the $3$ sequences. The next $3$ lines each contain a length-$n$ character sequence without spaces. Only lowercase letters a to z are used.

Output Format

One line with a positive integer $ans$, taken modulo $10^8$.

4   
aabb   
abab   
baba

5

Hint

Sample 1 Explanation

For the single sample, there are $5$ subsequences: a, ab, aa, bb, b.

Constraints and Conventions

• For $30\%$ of the testdata, it is guaranteed that $1 \le n \le 10$.
• For $70\%$ of the testdata, it is guaranteed that $1 \le n \le 50$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 150$.

Translated by ChatGPT 5