← 返回题目列表

AtCoder · aising2020_f

F. 两个潜弹

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给定的是一个整数 N。 Snuke 会选择整数 s_1, s_2, n_1, n_2, u_1, u_2, k_1, k_2, e_1,和 e_2 以便满足以下所有六个条件:

  • 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) 如下:
    • (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) is 1 和五个选择 (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1) is 2,所以答案是 11.
  • 一定要找到模数之和 (10^{9} +7).