---
# System prepended metadata

title: Pn. Angus的第一題

---


#                             Pn. Angus的第一題   
time limit per test : 1 second
memory limit per test : 256 megabytes

*這是程式的題目啦，但也可以當作一般的數學題喔
*我知道很不通順 請見諒== 考卷就長這樣


Angus 今天上數學課，正在學排列組合的他在考試中遇到一題連高宇也寫錯。
考試卷中本來的題目敘述如下 : 

:::success
**一個集合S={1,2,3,.....,10}, 
對其中每個元素進行取或不取，
求 至多只包含所有三個連續整數中其中一個數的機率。**

(答案是60喔嘻嘻)

(白話來說，
就是全部每10個數1~10中
每3個數字 : 123 234 ...當中，
只能在子集合中出現至多一個)(有1就不能2跟3)

:::



(Angus人很好，幫你們理解完題目了，譬如子集合 {1,7} 是符合的，而集合{5,6,10}則否。)

在老師說明完解法後，Angus認為這樣的題目已經滿足不了他，為了證明給高宇看自己的實力，他決定增加題目條件。

「一個集合S={1,2,3,.....,N}, 
對其中每個元素進行取或不取，
求 至多只包含所有 K 個連續整數中其中一個數的機率。」

但同時，Angus也是個好人，他認為算機率太麻煩了，因此他又把題目改成
.
.


:bug: :bug: :bug: :bug: :bug: :bug: 
:::success

***「一個集合S={1,2,3,.....,n}, 
對其中每個元素進行取或不取，
求 至多只包含所有 k 個連續整數中其中一個數可能的方式數量。」***


(白話來說，
就是全部n個數中
每k個數 : 12..k及23..k+1及..當中，
只能在子集合中出現至多一個數字)

:::


希望你們幫幫他，讓他在高宇面前抬的起頭

## INPUT
第一行有一個整數T(T<=1000),代表測資的數量。
每筆測資中都有正整數N 以及 K 分別對應上述題目的N K
(1<=K<=N<=200000)

## OUTPUT
每筆測資輸出一行ANS 後換行，ANS代表上述問題的可能數量。但由於答案可能不小，請對1e9+7取模後輸出。


## 範測TEST
:bulb:


:::success
Input
1
10 3

Output
60
:::

:::success
Input
1
1 1

Output
2
:::
:::success
Input
3
7 2
6 2
5 2

Output
34
21
13
:::
