9. 阿源的田地

阿源的田地

題目敘述

阿源從家裡拿來一張田地的地圖，長的如下圖 黑點代表可以種植的點，每個可以種植的點都跟相鄰的點距離為$1$ 當他拿給我們看時，一位對圍棋十分感興趣的同學說: 「啊，關我屁事。」 「關我屁事？」我說。 「關我屁事= =。」一位外號叫「大食客」的同學緊接著說。 我們不禁哄堂大笑，同樣的一張地圖，關其他人屁事。 阿源連忙把地圖收好，他覺得田地就是田地，關你們屁事？

阿源覺得田地荒廢已久，決定來種點東西，但阿源是個懶惰的人，所以他只決定要種三棵果樹就好 阿源特別的喜歡正三角形，所以想要將果樹種在三個點，使的這三個點形成一個正三角形。 但為了不要影響果樹生長，所以果樹間的距離必須大於$1$

他的田地為一個邊長為n的正三角形，請問共有幾種種植方式呢? 由於答案可能很大，請將他mod 1000000007

輸入說明

第一行會有一個整數Ｔ($\leq 100$)，代表有幾個田地。 接下來Ｔ行，每行會有一個正整數ｎ，代表田地的大小。

輸出說明

請輸出一個正整數，代表合法的植樹方法有幾種。

範例輸入

4 1 2 3 4

範例輸出

0 1 6 19

範例說明

$n=1$時，任兩點距離皆為1，所以沒有任何合法排法 $n=2$時，唯一合法放法為放三個角 $n=3$時，合法放法為下列6種

子題一[20%]

$n \leq 20$

子題二[30%]

$n \leq 1000$

子題三[40%]

$n \leq 10^6$

子題四[10%]

$n \leq 10^9$

Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 4