0 Judge
Code: 0
阿源從家裡拿來一張田地的地圖,長的如下圖
黑點代表可以種植的點,每個可以種植的點都跟相鄰的點距離為$1$
當他拿給我們看時,一位對圍棋十分感興趣的同學說:
「啊,關我屁事。」
「關我屁事?」我說。
「關我屁事= =。」一位外號叫「大食客」的同學緊接著說。
我們不禁哄堂大笑,同樣的一張地圖,關其他人屁事。
阿源連忙把地圖收好,他覺得田地就是田地,關你們屁事?
阿源覺得田地荒廢已久,決定來種點東西,但阿源是個懶惰的人,所以他只決定要種三棵果樹就好 阿源特別的喜歡正三角形,所以想要將果樹種在三個點,使的這三個點形成一個正三角形。 但為了不要影響果樹生長,所以果樹間的距離必須大於$1$
他的田地為一個邊長為n的正三角形,請問共有幾種種植方式呢? 由於答案可能很大,請將他mod 1000000007
第一行會有一個整數T($\leq 100$),代表有幾個田地。 接下來T行,每行會有一個正整數n,代表田地的大小。
請輸出一個正整數,代表合法的植樹方法有幾種。
$n=1$時,任兩點距離皆為1,所以沒有任何合法排法
$n=2$時,唯一合法放法為放三個角
$n=3$時,合法放法為下列6種
$n \leq 20$
$n \leq 1000$
$n \leq 10^6$
$n \leq 10^9$