学姐姐非常喜欢字符串，所以学弟送给了她两个字符串作为礼物。 两个字符串分别为$X，Y$。她非常开心，但在开心之余她还想考考学弟。 她定义$L$为$X$与$Y$的最长公共子序列的长度（子序列在字符串内不一定连续，一个长度为$L$的字符串有$2^L$个子序列，包括空子序列）。 现在学姐姐取出了$X$的所有长度为$L$的子序列，并要求学弟回答在这些子序列中，有多少个是$Y$的子序列。 因为答案可能很大，所以学弟只需要回答最终答案模$10^9 + 7$。
第一行包含一个整数$T$，表示测试数据组数。 对于每组测试数据： 第一行包含一个非空字符串$X$。 第二行包含一个非空字符串$Y$。 字符串由小写英文字母构成。 $1\leq |X|,|Y|\leq 1000$, $|X|$表示$X$的长度。
对于每组测试数据输出一个整数，表示对应的答案。
2 a b aa ab
1 2