F - Two Snuke 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

整数 N が与えられます。すぬけ君は整数 s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2 を以下の 6 つの条件の全てを満たすように選びます。

  • 0 \leq s_1 < s_2
  • 0 \leq n_1 < n_2
  • 0 \leq u_1 < u_2
  • 0 \leq k_1 < k_2
  • 0 \leq e_1 < e_2
  • s_1 + s_2 + n_1 + n_2 + u_1 + u_2 + k_1 + k_2 + e_1 + e_2 \leq N

ありうる (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2) の組すべてについて (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1) を計算し、その総和を (10^{9} +7) で割ったあまりを求めてください。

テストケースは T 個与えられるので、それぞれについて答えを求めてください。

制約

  • 与えられる入力は全て整数
  • 1 \leq T \leq 100
  • 1 \leq N \leq 10^{9}

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられる。

N

出力

T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。

入力例 1

4
4
6
10
1000000000

出力例 1

0
11
4598
257255556
  • N=4 のとき (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2) としてありうる組は存在しません。よって、答えは 0 です。
  • N=6 のとき (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2) としてありうる組は以下の 6 通りです。
    • (0,1,0,1,0,1,0,1,0,1)
    • (0,2,0,1,0,1,0,1,0,1)
    • (0,1,0,2,0,1,0,1,0,1)
    • (0,1,0,1,0,2,0,1,0,1)
    • (0,1,0,1,0,1,0,2,0,1)
    • (0,1,0,1,0,1,0,1,0,2)
  • (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1) の値が 1 となるものが 1 通り、2 となるものが 5 通りあるので、答えは 11 です。
  • (10^{9} +7) で割ったあまりを求める必要があることに注意してください。

Score : 600 points

Problem Statement

Given is an integer N. Snuke will choose integers s_1, s_2, n_1, n_2, u_1, u_2, k_1, k_2, e_1, and e_2 so that all of the following six conditions will be satisfied:

  • 0 \leq s_1 < s_2
  • 0 \leq n_1 < n_2
  • 0 \leq u_1 < u_2
  • 0 \leq k_1 < k_2
  • 0 \leq e_1 < e_2
  • s_1 + s_2 + n_1 + n_2 + u_1 + u_2 + k_1 + k_2 + e_1 + e_2 \leq N

For every possible choice (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2), compute (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1), and find the sum of all computed values, modulo (10^{9} +7).

Solve this problem for each of the T test cases given.

Constraints

  • All values in input are integers.
  • 1 \leq T \leq 100
  • 1 \leq N \leq 10^{9}

Input

Input is given from Standard Input in the following format:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

Each case is given in the following format:

N

Output

Print T lines. The i-th line should contain the answer to the i-th test case.

Sample Input 1

4
4
6
10
1000000000

Sample Output 1

0
11
4598
257255556
  • When N=4, there is no possible choice (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2). Thus, the answer is 0.
  • When N=6, there are six possible choices (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2) as follows:
    • (0,1,0,1,0,1,0,1,0,1)
    • (0,2,0,1,0,1,0,1,0,1)
    • (0,1,0,2,0,1,0,1,0,1)
    • (0,1,0,1,0,2,0,1,0,1)
    • (0,1,0,1,0,1,0,2,0,1)
    • (0,1,0,1,0,1,0,1,0,2)
  • We have one choice where (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1) is 1 and five choices where (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1) is 2, so the answer is 11.
  • Be sure to find the sum modulo (10^{9} +7).