2694. 最长公共子序列

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

令给定的字符序列 $X=x_0x_1…x_{m-1}$,序列 $Y=y_0y_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$ 个字符序列,都是大写字母组成,以 . 结束。

第 $2$ 行为第 $2$ 个字符序列,都是大写字母组成,以 . 结束。

注意,两个字符序列均不包含最后的 .

输出格式

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

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

数据范围

输入字符序列的长度都不超过 $5000$。

输入样例:

ABCBDAB.
BACBBD.

输出样例:

4
7