You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

求 $3$ 个字符序列有多少个不同的公共子序列。

Format

Input

第一行为一个正整数 $n$ ，表示 $3$ 个序列的长度。 （$1\leq n \leq 150$）

接下来 $3$ 行，每行一个无空格长度为 $n$ 的字符序列。只包含小写字母 $a$ 到 $z$。

Output

一个正整数 $ans$，表示有 $ans$ 个公共子序列，对 $10^8$ 取模。

Samples

4   
aabb   
abab   
baba

6

Explain

对于唯一的一个样例，有 $6$ 种子序列，分别是 $a，ab，aa，bb，b$ , 以及一个空序列。

Limitation

1s, 1024KiB for each test case.