TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

在王都之中,有兩個維持秩序、守護正義的組織--白薔薇與黑薔薇組織。
白薔薇的成員們有著如同家人一般的情誼,共同與潛伏在王都中的黑暗與邪惡戰鬥。
多虧了他們,人民才能無憂無慮地過活。
不過最近發生了怪事。
白薔薇的成員們在許多地方發生意外了!
像是被盛滿章魚的貨車壓到、掉進下水溝中、走到半路撞到牆......等等,通通被送進了醫院中。
這造成了白薔薇目前人手極為不足。
懷疑這其中有著陰謀的隊長,發現了其中似乎有所玄機。
精確來說,第$n$天受害人數正好會等於第$n-1$和第$n-2$天的受害人數總和。
已知第一天和第二天的受害者都是1人。
請你幫幫隊長算算看,如果到了第$n$天,白薔薇會有多少人進醫院呢?(你可以認定白薔薇有無限多的人,而且每個人進入醫院後都沒辦法出院但也不會死幫QQ)

Input Format

輸入的第一行包含一個正整數$q$代表有$q$筆詢問。
接下來$q$行每一行包含一個非負整數$n$代表要求的是截至第$n$天為止的受害者總和。

Output Format

對每一筆詢問,如果答案為$ans$,請輸出$ans \ mod \ 10^ 9+9$的值。

Sample Input

3
1
2
3

Sample Output

1
2
4

Hints

subtask 0:$q \leq 10 ,\ n \leq 10$
subtask 1:$q = 1000 ,\ n \leq 1000000$
subtask 2:$q = 10000 ,\ n \leq 10^ {18}$
如果找到題目敘述來源的話可以向我要hint喔><

Problem Source

Problem Set and Description by PolarisChiba

Subtasks

For Testdata: 0 ~ 0, Score: 50
For Testdata: 1 ~ 1, Score: 40
For Testdata: 2 ~ 2, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 65536
1 10000 65536 65536
2 10000 65536 65536