Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0012 - STAIRS

   There is a garden on the hillside, near one of the Alliance of Combinatorics Masters’s (ACM) building. Hill is steep, so each and every road in garden technically is a long stone stairs. Each step of the stairs has rectangular shape; all of them are paved with tiles – 1x2 rectangles. Width W of every step is 4, length N may vary.

   During usual walk one of the Masters found three steps of same size, paved in different ways. Now Master wonders, how many different ways there is to pave a step of known size. Please, help him find the answer.

Input

   First line of input file contains single number T (T ≤ 200) – number of test cases. Next T lines contain T test cases; each test case consists of single number N (1 ≤ N ≤ 103) – length of the step. Width of each step is fixed – 4.

Output

   For each test case print in different line single number – number of different ways of paving step Nx4; answer can be pretty big, so print it modulo 1 000 000 009

Examples

stdin

stdout

1

3

1

2

8

1

5

2245

   
   

Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2013-12-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.East Sibirean QF 2013.B

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.