Dai Ma Chu Shi
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Dai Ma Chu Shi is a Chinese CodeChef.
He recently got a huge chocolate with the size 2 × 2 × 2 × 2 × n. (Yes, in five-dimensional space).
He wants to cut it into 8n pieces of small chocolate of size 1 × 1 × 1 × 1 × 2 each. Please notice that the direction doesn't matter, 1 × 1 × 1 × 2 × 1 and 2 × 1 × 1 × 1 × 1 are acceptable.
He wants to know how many ways he can achieve this feat in. Because the answer is very large, please tell him the answer modulo 109+7.
First line of input contain a single integer T, the number of test cases. T tests follow. Each test case contain a single integer n.
For each test case output a single line containing the answer for the problem modulo 109+7.
- 1 ≤ T ≤ 1000
- 1 ≤ n ≤ 109
- Subtask 1 (30 points), n is a power of 2.
- Subtask 2 (70 points), Original constraints
Input: 1 1 Output: 272
I have discovered a truly marvellous enumeration of this, which this margin is too narrow to contain.
|Tags||gauss-elim hard jan16 recurrence wwwwodddd|
|Time Limit:||8 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.