# Practice on Toph

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

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

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 10^{9}+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 10^{9}+7.

Input | Output |
---|---|

11001 101 | 2 |

All distinct permutations of |