P1819 Common Subsequences

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

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.

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

#### 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