Two Snuke

AtCoder

IDaising2020_f

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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)$.

API Response (JSON)

{
  "problem": {
    "name": "Two Snuke",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "aising2020_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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:\n\n*   $0 \\leq...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments