Distinct Subsequence Occurrences

Given two strings s and t, your task is to count the number of distinct subsequences of t in s. A subsequence is a sequence that can be derived from the string s by deleting some (or no) characters without changing the order of the remaining characters.

Mathematically, if we define \( f(s, t) \) as the number of distinct subsequences of t in s, the recurrence can be written as:

[ f(i, j) = \begin{cases} 1, & \text{if } j = 0, \ f(i-1, j-1) + f(i-1, j), & \text{if } s_i = t_j, \ f(i-1, j), & \text{if } s_i \neq t_j, \end{cases} ]

where \( f(i, j) \) denotes the number of ways to form the first \( j \) characters of t from the first \( i \) characters of s.

Please implement your solution such that it reads input from standard input (stdin) and writes the output to standard output (stdout).

inputFormat

The input consists of two lines:

• The first line contains the string s.
• The second line contains the string t.

Note that the strings may be empty.

outputFormat

Output a single integer, which is the number of distinct subsequences of t found in s.

## sample

babgbag
bag

5

</p>