Counting Interpretations

Cjwssb misunderstood your thank you because he misheard some parts of your words. To clear the air you decide to tell him that the original sentence can be understood in several different ways. The idea is as follows:

Given an original sentence S and a heard sentence H, consider an interpretation as the result of replacing the words in S that correspond to H (in order) with an asterisk *. In other words, if the heard sentence H is a subsequence of the original sentence S, then for every distinct subsequence matching of H in S, we replace the matched words by * to form a new sentence with a new meaning.

Your task is to count the number of such distinct interpretations (i.e. the number of ways H can be found as a subsequence in S).

This can be computed using dynamic programming. Let S be composed of n words and H be composed of m words. Define the recurrence in \(\LaTeX\) as follows:

[ \text{dp}[i][j] = \text{dp}[i-1][j] + \Bigl[ S[i]=H[j] \Bigr] \times \text{dp}[i-1][j-1], \quad \text{for } 1 \le i \le n, ; 1 \le j \le m, ]

with the base conditions \(\text{dp}[i][0]=1\) for all \(0\le i\le n\) and \(\text{dp}[0][j]=0\) for \(j>0\). The answer is \(\text{dp}[n][m]\).

inputFormat

The input consists of two lines:

1. The first line is the original sentence S, with words separated by spaces.
2. The second line is the heard sentence H, with words separated by spaces.

outputFormat

Output a single integer representing the number of interpretations (i.e. the number of distinct ways H can be found as a subsequence in S).

sample

I love love you
love

2