TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

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

5
aa ab
zzzzz xxx
abcdefg hijklmno
shik eddy
wangyenjen coquelicot

Sample Output

7
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144