Longest Common Subsequence and Count

Given two character sequences $X=\{x_0,x_1,\cdots,x_{m-1}\}$ and $Y=\{y_0,y_1,\cdots,y_{n-1}\}$, a subsequence of a sequence is formed by deleting zero or more characters (not necessarily contiguous) from the sequence. A sequence $Z$ is a subsequence of $X$ if there exists a strictly increasing index sequence $\{i_0,i_1,\cdots,i_{k-1}\}$ such that for every $j=0,1,\cdots,k-1$, we have $x_{i_j}=z_j$. For example, if $X=\tt{ABCBDAB}$, then $\tt{BCDB}$ is a subsequence of $X$.

The task is to find the length of the longest common subsequence (LCS) of the two given sequences and count the number of distinct longest common subsequences. Two subsequences are considered the same if they result in the same string.

Formally, let $L$ be the length of the LCS. You need to compute:
[ L = \max{ k : \exists~{i_0,i_1,\cdots,i_{k-1}}, {j_0,j_1,\cdots,j_{k-1}} \text{ with } x_{i_p} = y_{j_p}~\forall p }, ]
and the number of distinct subsequences $S$ such that each $S$ is common to both sequences and has length $L$.

inputFormat

The input consists of two lines. The first line contains the first character sequence, and the second line contains the second character sequence. Both sequences consist of uppercase letters only.

outputFormat

Output two integers separated by a space: the length of the longest common subsequence and the number of distinct longest common subsequences.

sample

ABCBDAB
BDCABA

4 3