0018 - たぷ数

Problem

問題

ノエルちゃんはたぷ数が大好きです。

ここである値 $x$ について $x$ の各桁の数字を並び替えることによって回文, つまり前から読んでも後ろから読んでも同じ文字列にできるとき, その値がたぷ数であると定義します。 例えば $13333$ は, $33133$ のように並び替えると回文にできるためたぷ数です。同様に $100$ や $3$ についてもたぷ数です。 一方で $1333$ はどのように並び替えても回文にできないためたぷ数ではありません。

次の $Q$ 個のクエリに全て答えてください。

  • $L_i$ 以上 $R_i$ 以下の値のうち, たぷ数の個数を $10^9 + 7$ で割ったあまりで求める。

入力

$Q$
$L_1$ $R_1$
$L_2$ $R_2$
:
$L_Q$ $R_Q$

$1$ 行目にクエリの個数 $Q(1 \le Q \le 1000)$ が与えられます。

つづく $Q$ 行にはそれぞれのクエリの情報 $L_i, R_i(1 \le L_i \le R_i \lt 10^{1000})$ が与えられます。

出力

出力は $Q$ 行からなります。$i$ 行目には $i$ 番目のクエリの答えを出力してください。

入出力例

入力例

5
1 9
80 101
1000 1009
1333 133333333333333333333
10 10

出力例

9
4
1
373840419
0

$1$ 番目のクエリでは $1$ 以上 $9$ 以下の値全てがたぷ数です。

$2$ 番目のクエリでは $88, 99, 100, 101$ がたぷ数です。

$3$ 番目のクエリでは $1001$ がたぷ数です。

$4$ 番目のクエリについて, 答えを $10^9 + 7$ で割ったあまりで出力することに注意してください。

$5$ 番目のクエリでは たぷ数は $0$ 個です。