F. Droid Foundry B (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Separatists are still having trouble with the Geonosis Droid Foundry! The issue now is that the B2-series super battle droids are being produced with many unnecessary parts. Poggle the Lesser is even more displeased with this situation and he wants to know how this issue can be resolved.

You are given a string baseline $$$b$$$ which represents the parts for all droids as they come out of the production line. Every produced droid appears this way. You are also given a design string $$$d$$$ which represents how the droids should appear after modification. It is guaranteed that the design is at most as long as the baseline $$$(|d| \le |b|)$$$.

You are looking to remove zero or more characters from $$$b$$$ to produce $$$d$$$, without changing the order of the characters. However, because many parts depend on one another, no two adjacent characters can both be removed. Poggle the Lesser wants to know how many ways $$$d$$$ can be made using this method. Two ways are different if the sets of removed indices are different.

Determine how many different ways $$$d$$$ can be made by removing letters from $$$b$$$. As this result can get quite large, output this result modulo $$$10^9+7$$$.

Input

The first line of input contains the string $$$b$$$ $$$(1 \le |b| \le 500)$$$ — the baseline string consisting of uppercase letters [A-Z].

The second line contains the string $$$d$$$ $$$(1 \le |d| \le 500)$$$ — the design string also consisting of uppercase letters [A-Z].

Output

Output a single integer: the number of unique ways to remove characters from $$$b$$$ that result in $$$d$$$, while not removing two or more characters in a row.

Examples
Input
AAAAA
AAA
Output
6
Input
ABCABC
ABC
Output
0
Input
AABBCC
ABC
Output
4