A subsequence of s is chosen by picking a set of positions in increasing order and reading the characters at those positions. Two subsequences are considered different if they use different sets of positions, even if they spell the same text. Given strings s and t, count how many subsequences of s spell exactly t.
Input format
Line 1: the string s (possibly empty).
Line 2: the string t (possibly empty).
Both strings contain only lowercase letters a-z.
Output format
A single integer: the number of position-sets of s that spell t. If t is empty the answer is 1 (the empty selection).
Constraints
- 0 <= length of each string <= 500
- The answer fits in a signed 64-bit integer for every test.