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

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

以下是\(Ian\)發現的[廢破數列]定義

\(f_1 = 0\)
\(f_2 = 0\)
\(f_3 = 1\)
\(f_x = a*f_{x-3}+b*f_{x-2}+c*f_{x-1}\)

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

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

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

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

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

每天選一個整數\(q\)，代表當天要研究的組合數，接下來選出\(q\)個\(n\ a\ b\ c\)的組合並計算出

\(f_1 = 0\)
\(f_2 = 0\)
\(f_3 = 1\)
\(f_x=a*f_{x-3}+b*f_{x-2}+c*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\)行有四個整數\(n\ a\ b\ c\)

輸出說明

輸出\(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\)

子題配分