Count Secured Strings

Choose a subsequence of the customer password s by index, and count the choices that are lexicographically strictly greater than t, modulo 1000000007. When the same resulting string comes from different index choices, each is counted separately.

输入格式

Two lines, s and t; 1≤|s|≤100000, 1≤|t|≤100, both lowercase.

输出格式

Output a single integer answer.

样例 1

输入：

aba
ab

输出：

3

样例 2

输入：

bab
ab

输出：

5

样例 3

输入：

aaa
aa

输出：

1

样例说明

Example 1: the three choices b, ba and aba are strictly greater, so the answer is 3. Example 2: the two b's at different positions plus ba, bb and bab, 5 in total. Example 3: only the full aaa is greater than aa, so the answer is 1.