William 是一名從復旦國中直升上來的學生，

他經常跟那些外考的同學說起往事，

來幫助同學融入新環境。

以滿足他深不見底的虛榮心。

有一天，

他提起了國三時抬餐的時光，

他說：

「想當初我們都是爬樓梯，別班都有電梯可以座。」

這時旁邊的 Mark 就說：

「有什麼不好嗎？我們可是比他們有更多機會鍛鍊身體欸。」

不過如此壓抑的會考生活讓他們兩人有了奇怪的想法。

William：「你有想過如果我在寫題本時可以照順序寫，也可以跳一題寫，在寫 $N$ 題時有幾種方法可以把整本題本都翻完？」

Mark：「沒有欸，排組不是高一下的嗎？」

William：「你還是要會阿！」

Mark：「阿你怎麼不會。」

William：「……」

Mark：「算了，等等請 tree 幫你解答好了，他可是電到連清大物培躺著就會上的人！」

恰巧的是 tree 在家裡疊積木沒有來學校，

就請你們代替 tree 幫他們兩個人解答吧！

不過因為可能數太多了，

所以請把答案 $mod10^9+7$

本題有 $T$ 筆測資