$Ian$最近迷上了刷一中電研$judge$，寫完$judge$上所有題目的他，總共寫了高達四題費氏數列的題目，他決定在期末考前開始著手研究費波那契數列。

經過他不懈的努力，他找出一個特別的數列，但他認為這完全無法與費氏數列相比，所以他一氣之下把他發現的數列命名為"廢破數列"。

以下是$Ian$發現的[廢破數列]定義

$f_1=0$
$f_2=0$
$f_3=1$
$f_x=a\ast f_{x-3}+b\ast f_{x-2}+c\ast f_{x-1}$

幾千年後，$Ian$研究廢破數列的資料被$teddybear$發現。

$teddybear$發現這數列在某個$abc$組合下某一項的值列出來後，竟然僅僅是看著這串數字，腦中就會浮現神秘的旋律 各位可以感受一下

時間回到$12/3124:00$，正在跨年的$Ian$眼前一黑，倒在電腦桌前。當他緩緩張開他的眼睛，映入眼簾的竟然是傳說中的媽祖$!$！

媽祖$!$告訴他:$Ian$，我是媽祖階層，你發現的"廢破數列"中某個$abc$的組合的第$n$項將是拓展人類對數字認知的關鍵。

從此$Ian$踏上了他研究"廢破數列"的旅程，由於他只是高中生，時間有限，所以他制定了一套研究方法。

每天選一個整數$q$，代表當天要研究的組合數，接下來選出$q$個$nabc$的組合並計算出

$f_1=0$
$f_2=0$
$f_3=1$
$f_x=a\ast f_{x-3}+b\ast f_{x-2}+c\ast f_{x-1}$
時$f_n$的值。

輸入$q$和$q$個$n_i{a}_i{b}_i{c}_i$，請計算$lan$ $q$個研究出的數字。由於答案可能很大，請輸出對${10}^9+7$取模後的答案。

$1\le q\le {10}^5$
$1\le n\le {10}^9$
$0\le a,b,c\le {10}^5$

輸入說明

第一行有一個整數$q$
接下來有$q$行，第$i$行有四個整數$nabc$

輸出說明

輸出$q$行 第$i$行為第$i$個組合的答案

範例輸入

3
5 1 1 1
6 1 2 3
6 4 5 6

範例輸出

2
40
280

範例說明

根據上述定義式，當
$a=1,b=1,c=1$時
$f_5$ 會是$2$
$a=1,b=2,c=3$時
$f_6$ 會是$40$
$a=4,b=5,c=6$時
$f_6$ 會是$280$

子題配分