Ali is studying for his last midterm exam. but he is so afraid of this exam as this subject is so hard for him, there are only $n$ hours left for this exam. and he wants to make a plan for studying and eating to be able to focus on the exam, He can do one of two things, either study or revise one lecture, which will take a whole hour, or eat fast food, which will take two hours.
For example, if Ali has $5$ hours left, one possible schedule is $SESS$, which means he will study for one hour, eat for two hours, study for one hour, and study for one hour, for a total of $5$ hours. He could also choose one of the following plans: $SSSSS$, $ESSS$, $SSES$, $SSSE$, $SEE$, $ESE$, and $EES$.
Ali realized that there are a lot of ways that he can schedule the studying plan. so he asked you to help him count the number of ways?
Note that the number of ways could be very large, so you should print the remainder by dividing it by $10^9+7$.
The input consists of multiple test cases. The first line contains a single integer $t (1 \le t \le 10^5)$ --- the number of test cases.
Each test case contains only one integer $n(1 \le n \le 10^6)$---the remaining hours for Ali's exam.
For each test case, print one integer $M$, the number of ways to schedule a studying plan in $N$ hours, after taking the remainder of dividing it by $10^9+7$.
| Input | Output |
|---|---|
3 1 2 3 Copy
|
1 2 3 Copy
|
On the first day, we don't have any choice but to study for one hour: S
On the second day, we have two choices, study for two hours or eat one meal: SS, E
On the third day, we need to take the valid combinations of Study, which lasts for 1 hour, and the valid combinations of Eat, which lasts for 2 hours. We can calculate them from both the first and second day.
Our state $dp[i]$ will represent the number of valid combinations that can be found at $dp[i-1]$ and $dp[i-2]$
In conclusion, the answer to the problem is the Fibonacci of $n$.