Count Pattern Subsequences

Given two strings, (T) (text) and (P) (pattern), count the number of times the pattern appears as a subsequence in the text. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the order of the remaining characters.

The solution can be computed using dynamic programming. Let (dp[i][j]) represent the number of ways to form the first (i) characters of (P) using the first (j) characters of (T). The recurrence is given by:

[ \displaystyle dp[i][j] = \begin{cases} dp[i-1][j-1] + dp[i][j-1], & \text{if } P[i-1] = T[j-1], \ dp[i][j-1], & \text{otherwise}. \end{cases} ]

The base case is (dp[0][j] = 1) for any (j), since the empty pattern is a subsequence of any string exactly once.

inputFormat

The input consists of two lines. The first line contains the text string (T) and the second line contains the pattern string (P). Both strings may contain spaces and other printable characters.

outputFormat

Output a single integer representing the number of times the pattern appears as a subsequence in the text.## sample

abcabc
abc

4