Comet OJ

C1407 [HAOI2010]最长公共子序列

内存限制：256 MB 时间限制：1000 ms

题目描述

字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。

令给定的字符序列 $X=$"$x_0,x_1,…,x_{m-1}$"，序列 $Y=$"$y_0,y_1,…,y_{k-1}$" 是 $X$ 的子序列，存在 $X$ 的一个严格递增下标序列 $<i_0,i_1,…,i_{k-1}>$，使得对所有的 $j=0,1,…,k-1$，有 $x_{i_j} = y_j$。

例如，$X=$ "ABCBDAB"，$Y=$ "BCDB" 是 $X$ 的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。

输入格式

第 $1$ 行为第 $1$ 个字符序列，都是大写字母组成，以.结束。长度小于 $5000$。

第 $2$ 行为第 $2$ 个字符序列，都是大写字母组成，以.结束，长度小于 $5000$。

输出

第 $1$ 行输出上述两个最长公共子序列的长度。

第 $2$ 行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对 $100,000,000$ 求余即可。

样例

样例输入 1

ABCBDAB.
BACBBD.

样例输出 1

4
7

提示