1169. Distinct Subsequences — Count

Given strings s and t, return the number of distinct subsequences of s that equal t. The input is JSON {s, t}.

Input: JSON {s, t}.

Output: Integer — the number of distinct subsequences.

Examples

Example 1

Input: {"s":"rabbbit","t":"rabbit"}
Output: 3
Explanation: Three ways to form 'rabbit'.

Example 2

Input: {"s":"babgbag","t":"bag"}
Output: 5
Explanation: Five ways to form 'bag'.

Example 3

Input: {"s":"aaa","t":"a"}
Output: 3
Explanation: Three single a's.