Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Distinct Permutations

By foyaz05 · 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



Discussion
Statistics

62% Solution Ratio

SwampFireEarliest, 1M ago

nahid08Fastest, 0.2s

SwampFireLightest, 2.9 MB

AnachorShortest, 1148B

Submit

Login to submit