D-Double Strings_2021牛客暑期多校训练营5

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Given two strings $A, B_{}$ , and little H wants to choose a subsequence from $\{1, 2, \cdots, |A|\}$ (call it $a_{}$ ) and from $\{1, 2, \cdots, |B|\}$ (call it $b_{}$ ) respectively. A scheme is called good iff $|a| = |b_{}|$ and $\exists i \in \{1, 2, \cdots, |a|\}, A_{a_i} < B_{b_i}, \forall j \in \{1, 2, \cdots, i-1\}, A_{a_j} = B_{b_j}$ . Print the number of good schemes modulo $10^9+7$ .

输入描述:

The first line contains a string .

The second line contains a string .

It's guaranteed that  and  only contain lowercase letters.

输出描述:

Output one line only containing one integer, denoting the answer.

示例1

输入

复制

ib
coe

输出

复制

说明

For the first case, the 5 good schemes are:

示例2

输入

复制

banana
apple

输出

复制