代码最短的一集

题目描述

题目长度也要最短....

给定一个整数n(3=<n<=1e8),我们要将1~3n这3n个整数填入一个3 x n的矩阵之中,每个整数仅能填一次,找出一种填入方式,使得该矩阵的short值最大,输出最大short值.

定义: short值 指这个矩阵所有相邻的两个元素的代数和的总和(结合样例解释理解)

输入格式

第一行为一个正整数T

接下来T行,每行一个整数n

输出格式

包括T行,每行一个整数(答案对1e9+7进行取模)

样例

样例输入

5
3
4
5
100
10000

样例输出

134
247
392
160087
600009980

样例举例说明

5 4
3 2
对于上述矩阵的short值为(5+4)+(5+3)+(3+2)+(4+2)=28
1 2
3 4
5 6
对于上述矩阵的short值为(1+2)+(3+4)+(5+6)+(1+3)+(3+5)+(2+4)+(4+6)

当n==4时
1 2 3 4
8 7 6 5
9 10 11 12
这是一种正确的填入方式,因为1~3n这3n个整数各自都填入了一次
1 2 3 4
5 6 7 8
9 10 10 10 
显然这是一种不符合题意的填入方式