[HAOI2010]最长公共子序列

字符序列的子序列，是指从给定字符序列中删除若干个字符（也可以不删除任何字符）后形成的字符序列，被保留的字符之间不要求连续。

设字符序列为 $X=x_0x_1\cdots x_{m-1}$。若字符序列 $Y=y_0y_1\cdots y_{k-1}$ 是 $X$ 的子序列，则存在一个严格递增的下标序列 $\langle i_0,i_1,\ldots,i_{k-1}\rangle$，使得对于所有 $0\le j<k$，均有 $x_{i_j}=y_j$。例如，$X=\text{ABCBDAB}$，$Y=\text{BCDB}$，则 $Y$ 是 $X$ 的一个子序列。

对于给定的两个字符序列，设它们的最长公共子序列长度为 $L$。一个最长公共子序列匹配方案由两组严格递增的下标序列

$$\langle i_0,i_1,\ldots,i_{L-1}\rangle$$

和

$$\langle j_0,j_1,\ldots,j_{L-1}\rangle$$

构成，并且对于所有 $0\le t<L$，均有 $x_{i_t}=y_{j_t}$。

请计算 $L$ 以及满足条件的匹配方案数。即使两个方案得到的字符序列相同，只要任意一组下标序列不同，就视为不同方案。当 $L=0$ 时，两组空下标序列构成唯一的匹配方案。

输入格式

第 $1$ 行包含第 $1$ 个字符序列，由大写英文字母组成，并以字符 . 结束。

第 $2$ 行包含第 $2$ 个字符序列，由大写英文字母组成，并以字符 . 结束。

输出格式

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

第 $2$ 行输出最长公共子序列匹配方案数。答案可能很大，输出其对 $10^8$ 取模的结果。

样例输入

ABCBDAB.
BACBBD.

样例输出

4
7

数据范围

• 每个字符序列的长度均不超过 $5000$，不包含末尾的字符 .；
• 两个字符序列均只包含大写英文字母。

来源与许可

本题为 HAOI 2010 试题「最长公共子序列」，题面与测试数据整理自 BZOJ。

样例 1

输入

ABCBDAB.
BACBBD.

输出

4
7