You are given two binary strings A and B. Recall that binary string is a non-empty sequence of characters where each character is either '0' or '1'.
Find the number of distinct permutations of string B which are also subsequence of string A. As this number may be too large, you need to find its remainder modulo 109+7.
The first line contains a binary string A (1 ≤ length of A ≤ 700) and the second line contains a binary string B (1 ≤ length of B ≤ 700).
Each of the strings contains the characters '0' or '1'.
Output the answer modulo 109+7.
Input | Output |
---|---|
11001 101 | 2 |
All distinct permutations of 101 are 011,101,110 . But only 101 and 110 occur as subsequence of the string 11001 |