Given two strings s and t, return the number of distinct subsequences of s which equals t.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters.

Example 1:

Input:
rabbbit
rabbit
Output: 3

Example 2:

Input:
babgbag
bag
Output: 5

Constraints:

• 1 ≤ s.length, t.length ≤ 1000
• s and t consist of English letters

Input format: Two lines: s, then t.

Output format: Number of distinct subsequences.