样例下载

问题描述

有两个由小写字母组成的字符串 $s,t$。你需要计算对于 $s$ 的所有排列（相同字母不加区分），$t$ 在其中出现的次数总和是多少。

注意 aaa 在 aaaa 中出现了两次。

由于答案可能很大，你只需要输出答案 ${} \bmod 1000000007$ 的值。

输入包含多组数据。

输入格式

输入的第一行包含一个整数 $T$，表示数据组数。

接下来 $2T$ 行，每两行为一组，每行包含一个字符串，表示每组数据的 $s$ 和 $t$。

输出格式

输出包含 $T$ 行，每行一个整数，表示一个询问的答案。

输入输出样例

输入

2
aab
ab
aabb
ab

输出

2
6

数据规模与约定

对于 $20\%$ 的数据，$\left|s\right|\le 8$，其中 $|s|$ 表示字符串 $s$ 的长度；

对于另外 $30\%$ 的数据，$\left|s\right|\le 2000$，且 $s,t$ 仅可能包含 a b 两种字母；

对于再另外 $20\%$ 的数据，$s,t$ 仅可能包含 a b 两种字母；

对于 $100\%$ 的数据，$T\le100$，$1\le\left|t\right|\le\left|s\right|\le 100000$，$s,t$ 仅包含小写字母。