Description

在遠方的艦北殿茲小島上,聚集了炸魚四人眾AaW, BrineTw, yungyao, willychan,他們所產生的電場,如同霸王色霸氣一樣能纏繞在身邊,凡是靠近的閒雜人等,都會被炸的金黃酥脆。如果具有電場的兩人過於靠近,更會引發大爆炸!

好巧不巧的,他們搭上了同一班火車,具有電場的兩人若處在相同或相鄰的車廂中,便會因為距離太近而將列車給炸飛了。於是,作為列車長的你為了維護乘客安全必須重新編排座位。

為了避免以後發生更多緊急情況,你決定解決以下的問題:

共有$a$個帶有電場的人、列車有$b$節車廂。
其中帶有電場的人必須坐在不同、且不相鄰的車廂。
請問身為列車長且精通排列組合的你,共有幾種安排座位的方法?

你問我為什麼列車長不會被炸魚四人眾給炸飛?我也不知道。

Input Format

第一行有一個正整數$q$,代表總共有$q$筆詢問。
接下來有$q$行,每行有兩個正整數$a, b$。
$1\le q \le 10 ^ 6$
$1\le a \le b \le 10 ^ 6$

Output Format

請輸出$q$行,每行輸出安排座位的方法數( 由於答案可能很大,請將答案$mod\ 10 ^ 9 + 7$ )。

Sample Input 1

2
1 1
2 2

Sample Output 1

1
0

Sample Input 2

1
4 10

Sample Output 2

840

Hints

需要一些酷酷的排列組合(?
如果數字太大,模運算下不能直接用除法ㄛ!

Subtasks

No. Testdata Range Constraints Score
1 0~4 $1 \le q \le 10,\ 1 \le b \le 20$ 5
2 5~9 $1 \le a \le 2$ 12
3 10~14 $1 \le b \le 1000$ 33
4 15~19 無特別限制 50

TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

83.3% (5/6)

Tags

Problem Source

111學年度建北電資指定科目考試【資訊科上機考】

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 2
6 1000 65536 65536 2
7 1000 65536 65536 2
8 1000 65536 65536 2
9 1000 65536 65536 2
10 1000 65536 65536 3
11 1000 65536 65536 3
12 1000 65536 65536 3
13 1000 65536 65536 3
14 1000 65536 65536 3
15 1000 65536 65536 4
16 1000 65536 65536 4
17 1000 65536 65536 4
18 1000 65536 65536 4
19 1000 65536 65536 4
20 1000 65536 65536
21 1000 65536 65536
22 1000 65536 65536
23 1000 65536 65536
24 1000 65536 65536
25 1000 65536 65536
26 1000 65536 65536
27 1000 65536 65536
28 1000 65536 65536
29 1000 65536 65536