261. Distinct Subsequences (Count Target in Source)

Given two strings s and t, return the number of distinct subsequences of s which equal t, modulo 10^9+7. Input: '"s", "t"'.

Input: '"s", "t"'.

Output: Integer — count mod 10^9+7.

Examples

Example 1

Input: "rabbbit", "rabbit"
Output: 3
Explanation: Three ways to pick 'rabbit'.

Example 2

Input: "babgbag", "bag"
Output: 5
Explanation: Five subsequences equal 'bag'.

Example 3

Input: "abc", ""
Output: 1
Explanation: Empty target: one way.