countSecurePasswordVariations

Among all index subsequences of customer, count those that are lexicographically strictly greater than system. Identical strings chosen from different indices are counted separately; when system is a prefix, the longer string is greater. Output the result modulo 10⁹+7.

输入格式

Two lines with the lowercase strings customer and system, of lengths 1..100000 and 1..100 respectively.

输出格式

Output a single integer answer.

样例 1

输入：

bab
ab

输出：

5

样例 2

输入：

aa
a

输出：

1

样例 3

输入：

a
z

输出：

0

样例说明

Example 1: the two b at different indices, plus ba, bb, bab, 5 in total. Example 2: only aa is greater than a; the two single a are equal, so the answer is 1. Example 3: a is smaller than z, so there is no qualifying subsequence, and the answer is 0.