Distinct Subsequences

Problem statement

An archival search counts how many different sets of retained positions in a source transcript produce a target transcript. Two selections count separately even if they remove identical-looking repeated letters from different positions. Your task Count distinct subsequences of s that equal t. A subsequence retains positions in order and may delete any other positions. Important details Count choices of source indices, not distinct resulting text strings. An empty target has one match: retain no positions. A nonempty target cannot be formed from an empty source. The final answer fits a signed 32-bit integer. Worked example For s = aaa and t = aa, choose positions (0,1), (0,2) or (1,2). There are three matching subsequences.

Input format

Two full lines: s then t; either may be empty.

Output format

Print the number of matching subsequences.

Constraints

0 <= lengths <= 1000; English letters; final answer <= 2147483647.

Sample input

aaa
aa

Sample output

3