2126 . 一個配爾子序列
TopCoder
Tags
Description
對於兩個字串 $S, T$，若可以把 $T$ 的某些字元刪除後得到 $S$，我們就說 $S$ 是 $T$ 的子序列。
給你兩個字串 $A, B$，請你判斷有多少個字串配對 $(S_A, S_B)$，使得 $S_A$ 是 $A$ 的子序列、$S_B$ 是 $B$ 的子序列，而且 $S_A < S_B$。這裡的小於符號指的是字典順序，也就是說 $S_A$ 的字典順序要比 $S_B$ 的字典順序來得前面。
為了方便起見，我們定義空字串也是任意字串的子序列喔！
Input Format
第一行有一個正整數 $T$，代表總共有幾筆測試資料。 每筆測試資料為一行，包含兩個由小寫英文字母組成的字串 $A, B$。
- $1 \le T \le 50$
- $1 \le |A|, |B| \le 300$
Output Format
對於每筆測試資料，請輸出一行一個整數，代表符合題目要求的字串配對數除以 $1000000007$ 的餘數。字串配對不應該被重複計算。
Sample Input 1
5
aa ab
zzzzz xxx
abcdefg hijklmno
shik eddy
wangyenjen coquelicot
aa ab
zzzzz xxx
abcdefg hijklmno
shik eddy
wangyenjen coquelicot
Sample Output 1
7
3
32640
26
306171
3
32640
26
306171
Hints
- 第一筆測試資料包含 7 個 pair: (空字串, a), (空字串, b), (空字串, ab), (a, ab), (a, b), (aa, ab), (aa, b) 總共 7 個。
- 第二筆測試資料包含 3 個 pair: (空字串, x), (空字串, xx), (空字串, xxx) 總共 3 個。
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|