E. 到底有多少个公共子序列

    Type: Default 1000ms 256MiB

到底有多少个公共子序列

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

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

Format

Input

第一行为一个正整数 nn ,表示 33 个序列的长度。 (1≤n≤1501\leq n \leq 150)

接下来 33 行,每行一个无空格长度为 nn 的字符序列。只包含小写字母 aa 到 zz。

Output

一个正整数 ansans,表示有 ansans 个公共子序列,对 10810^8 取模。

Samples

4   
aabb   
abab   
baba
6

Explain

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

Limitation

1s, 1024KiB for each test case.

2025新生第一次周赛

Not Attended
Status
Done
Rule
XCPC
Problem
8
Start at
2025-11-8 14:00
End at
2025-11-8 17:00
Duration
3 hour(s)
Host
Partic.
30