Description

有一次,喵喵喵正在參加101登高賽,但因為要爬101樓,所以他很無聊

在他爬樓梯的時候,他發現他可以一次走一個階梯,也可以走兩個階梯

於是他好奇,如果從1樓爬到101樓的話,可以有幾種走法!

所以請你寫一個程式算出有幾種走法

Input Format

每筆測資的第一行有一個數字 q ,1 <= q <= 10000

2~q+1行有一個數字 a,1 <= a <= 10000

Output Format

請你將從第一階走到第a階的方法數模(%)1000000007後輸出

每個答案用換行間隔

Sample Input 1

3
5
4
10

Sample Output 1

8
5
89

Hints

C/C++ 要用unsigned long long喔

Subtasks

No. Testdata Range Score
1 0~9 100

TopCoder

cjtsai
$\begin{figure}[h] \centering \includegraphics[width=0.7\textwidth]{https://iscoj.fg.tp.edu.tw/images/banner_new.png} \caption{abb\label{thename}} \end{figure}$

User's AC Ratio

91.3% (21/23)

Tags

Problem Source

原百十 CKEISC Judge 010

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1000 250000 250000 65536 1
1 1000 250000 250000 65536 1
2 1000 250000 250000 65536 1
3 1000 250000 250000 65536 1
4 1000 250000 250000 65536 1
5 1000 250000 250000 65536 1
6 1000 250000 250000 65536 1
7 1000 250000 250000 65536 1
8 1000 250000 250000 65536 1
9 1000 250000 250000 65536 1