最长公共子序列 ### 题目描述 字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列 $X=\{x_0,x_1,\cdots ,x_{m-1}\}$，序列$Y=\{y_0,y_1,\cdots ,y_{k-1}\}$ 是 $X$ 的子序列，存在 $X$ 的一个严格递增下标序列 $\{i_0,i_1,\cdots,i_{k-1}\}$ ，使得对所有的$j=0,1,\cdots,k-1$ ，有 $x_{ij}=y_j$ 。例如，$X$=`ABCBDAB` ，$Y$=`BCDB` 是 $X$ 的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度，以及最长公共子序列个数。 ### 输入描述 第一行为第一个字符序列，都是大写字母组成，以 . 结束。长度小于 $5000$。 第二行为第二个字符序列，都是大写字母组成，以 . 结束，长度小于 $5000$。 ### 输出描述 第一行输出上述两个最长公共子序列的长度。 第二行输出所有可能出现的最长公共子序列个数，答案可能很大，只要将答案对 $1 \times 10^8$ 求余即可。 ### 输入输出样例 #### 示例 1 >输入 ```txt ABCBDAB. BACBBD. ``` >输出 ```txt 4 7 ```