Distinct Permutations

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

11001
101

2