题目描述

求有多少种长度为 $ n $ 的序列 $ A $，满足以下条件：

• $ 1 \sim n $ 这 $ n $ 个数在序列中各出现了一次；
• 若第 $ i $ 个数 $ A_i $ 的值为 $ i $，则称 $ i $ 是稳定的。序列恰好有 $ m $ 个数是稳定的。

满足条件的序列可能很多，序列数对 $ 10 ^ 9 + 7 $ 取模。

输入格式

第一行一个数 $ T $，表示有 $ T $ 组数据。
接下来 $ T $ 行，每行两个整数 $ n $、$ m $。

输出格式

输出 $ T $ 行，每行一个数，表示求出的序列数。

样例

input

5
1 0
1 1
5 2
100 50
10000 5000

output

0
1
20
578028887
60695423

数据范围与提示

测试点 1 ~ 3：$ T = 1000 $，$ n \leq 8 $，$ m \leq 8 $；
测试点 4 ~ 6：$ T = 1000 $，$ n \leq 12 $，$ m \leq 12 $；
测试点 7 ~ 9：$ T = 1000 $，$ n \leq 100 $，$ m \leq 100 $；
测试点 10 ~ 12：$ T = 1000 $，$ n \leq 1000 $，$ m \leq 1000 $；
测试点 13 ~ 14：$ T = 500000 $，$ n \leq 1000 $，$ m \leq 1000 $；
测试点 15 ~ 20：$ T = 500000 $，$ n \leq 1000000 $，$ m \leq 1000000 $。