{"raw_statement":[{"iden":"problem statement","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 s_1 < s_2$\n*   $0 \\leq n_1 < n_2$\n*   $0 \\leq u_1 < u_2$\n*   $0 \\leq k_1 < k_2$\n*   $0 \\leq e_1 < e_2$\n*   $s_1 + s_2 + n_1 + n_2 + u_1 + u_2 + k_1 + k_2 + e_1 + e_2 \\leq N$\n\nFor 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)$.\nSolve this problem for each of the $T$ test cases given."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq T \\leq 100$\n*   $1 \\leq N \\leq 10^{9}$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N$"},{"iden":"sample input 1","content":"4\n4\n6\n10\n1000000000"},{"iden":"sample output 1","content":"0\n11\n4598\n257255556\n\n*   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$.\n*   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:\n    *   $(0,1,0,1,0,1,0,1,0,1)$\n    *   $(0,2,0,1,0,1,0,1,0,1)$\n    *   $(0,1,0,2,0,1,0,1,0,1)$\n    *   $(0,1,0,1,0,2,0,1,0,1)$\n    *   $(0,1,0,1,0,1,0,2,0,1)$\n    *   $(0,1,0,1,0,1,0,1,0,2)$\n*   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$.\n*   Be sure to find the sum modulo $(10^{9} +7)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}