現在已經來到 $2021$ 年 $11$ 月，
身為副初階教學的 Hank 正回想著他的高一生活。
想想去年發生過的事......雖然不像某國家的高中生一樣，
一下轉生異世界，一下會被莫名其妙地殺死，還會莫名其妙地復活，
但是......首先發現自己被發去有國家棟樑的班、
整年都被 $COVID-19$ 搞、每天戴口罩、
當了 $108 課綱$ 第二屆白老鼠、
發現自己是復旦末屆直升班、上了始業輔導、
考上初階班、不到三個月就去進階班、
去了十分瀑布、寫了 $Discord$ $Bot$、
發下二類三類選組單、二類三類取消變成要成立醫科班、
醫科班不知為何只有 28 人填因此不成班、
$COVID-19$ 在台灣爆發連續一個星期每日破百例、史無前例的遠距教學，每天在電腦前 $6$ ~ $8$ 小時......
奇怪，聽說高一生活不是應該風平浪靜嗎？！
因為看到前面的 tree 和 revival 算著未來的選法算得很辛苦，所以他決定想他到底是如何走到現在的就好。
Hank 發現他的人生事件是線性的，也就是：對於每個事件，他只能選擇要經歷還是跳過，
假設他出生是他的人生第 $0$ 個事件，
由於上帝想要勞其筋骨，餓其體膚，所以他限制 Hank 最多只能連續跳過 $n$ 個事件。
舉例：假設 Hank 經歷了第 $5$ 個事件，那麼 Hank 如果跳過了第 $6$ ~ $n + 5$ 個事件，那麼 Hank 必須經歷第 $n + 6$ 個事件。
這天，擁有未來視的 Hank 發現：他今天會被他人告白，
由於他真的很想經歷這個事件，所以他想算出從第 $1$ 個事件到現在，
有幾種經歷事件的方法，讓 Hank 可以經歷被告白的第 $k$ 個事件？
(註：第一個事件也是可以跳過的)
第一行有一正整數 $T$，代表單一測資點有 $T$ 筆測資。
第 $2$ ~ $T + 1$ 行，每行依序有兩數 $n$, $k$。
對於每個 $n$, $k$，輸出經歷事件的方法數。
由於方法數可能很多，請將答案 $mod\;10^9 + 7$ 再輸出。
($mod$ 是取餘數的意思，初階班的各位以後可能很常看到喔~)
3 2 4 1 3 3 3
7 3 4
$30\%$ 測資，$n \leq 2$, $k \leq 30$
$60\%$ 測資，$n \leq 5$, $k\leq 10^5$
$90\%$ 測資，$n \leq 10$, $k \leq 10^7$
$100\%$ 測資，$1\leq n \leq 20$, $1\leq k \leq 10^{15}$, $1\leq T \leq 10$
對於範例第一筆測資，方法分別為：
1 -> 2 -> 4
1 -> 2 -> 3 -> 4
1 -> 3 -> 4
2 -> 3 -> 4
2 -> 4
3 -> 4
1 -> 4
共 $7$ 種
在宣告 1000000007 時，使用 const int mod = 1000000007; 可以使程式執行效率更高喔！
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||