Distinct Permutations

foyaz05 Contest Based on SUST Int...
Limits 2s, 256 MB

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.

Input

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

Output the answer modulo 109+7.

Sample

InputOutput
11001
101
2

All distinct permutations of 101 are 011,101,110 . But only 101 and 110 occur as subsequence of the string 11001


Submit

Login to submit.

Statistics

73% Solution Ratio
SwampFireEarliest, Dec '19
nahid08Fastest, 0.2s
SwampFireLightest, 2.9 MB
AnachorShortest, 1148B
Toph uses cookies. By continuing you agree to our Cookie Policy.