Count Subsequences

You are given two strings S and T. Your task is to determine the number of distinct subsequences of S that equal T.

A subsequence of a string is obtained by deleting zero or more characters without changing the order of the remaining characters. Formally, if we denote by \(dp[i][j]\) the number of subsequences of the first \(i\) characters of \(S\) that equal the first \(j\) characters of \(T\), then the recurrence is defined as:

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

Note that when \(T\) is an empty string, there is exactly one subsequence of \(S\) that equals \(T\).

inputFormat

The input consists of two lines. The first line contains the string S and the second line contains the string T.

outputFormat

Output a single integer which is the number of distinct subsequences of S that equal T.

rabbbit
rabbit

3