在遠方的艦北殿茲小島上,聚集了炸魚四人眾AaW, BrineTw, yungyao, willychan,他們所產生的電場,如同霸王色霸氣一樣能纏繞在身邊,凡是靠近的閒雜人等,都會被炸的金黃酥脆。如果具有電場的兩人過於靠近,更會引發大爆炸!
好巧不巧的,他們搭上了同一班火車,具有電場的兩人若處在相同或相鄰的車廂中,便會因為距離太近而將列車給炸飛了。於是,作為列車長的你為了維護乘客安全必須重新編排座位。
為了避免以後發生更多緊急情況,你決定解決以下的問題:
共有$a$個帶有電場的人、列車有$b$節車廂。
其中帶有電場的人必須坐在不同、且不相鄰的車廂。
請問身為列車長且精通排列組合的你,共有幾種安排座位的方法?
你問我為什麼列車長不會被炸魚四人眾給炸飛?我也不知道。
第一行有一個正整數$q$,代表總共有$q$筆詢問。
接下來有$q$行,每行有兩個正整數$a, b$。
$1\le q \le 10 ^ 6$
$1\le a \le b \le 10 ^ 6$
請輸出$q$行,每行輸出安排座位的方法數( 由於答案可能很大,請將答案$mod\ 10 ^ 9 + 7$ )。
需要一些酷酷的排列組合(?
如果數字太大,模運算下不能直接用除法ㄛ!
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 |