Problem K
Tree Planting
Bob’s favourite hiking trail was recently destroyed in a forest fire. Determined to help restore the forest, he begins planting saplings to reclaim what was lost. However, due to chronic back pain, Bob will plant one sapling per year, and he will continue this routine indefinitely.
The trees grow according to the following rules:
-
A newly planted sapling takes 1 year to grow into an adult tree.
-
After 2 additional years, the adult tree becomes mature.
-
As soon as a tree becomes mature, it immediately sheds a seed and plants a new sapling.
Each mature tree continues to plant one new sapling every year including the first. Each event (trees turning into an adult, trees getting planted, etc.) will happen at the same time at the start of each year.
For example, if there were $30$ mature trees in year $y$ and $12$ adult trees became mature trees between year $y$ and year $y+1$, then there would be $42$ mature trees and $43$ saplings, including the one from Bob, in year $y+1$.
Adult trees are those that are at least 1 year old but less than 3 years old (grown but not yet mature). Mature trees are not considered adult trees.
Given a year $y$, how many adult trees are there?
Input
The first line of input contains a single integer $n$ ($1 \leq n \leq 100\, 000$), the number of queries.
The next $n$ lines each contain a single integer $y$ ($0 \leq y \leq 10\, 000\, 000$), representing the year for which we want to determine the number of adult trees.
Output
Print $n$ lines, one for each query. Each line should contain the number of adult trees in year $y$, taken modulo $1\, 000\, 000\, 007$ (since the numbers can be very big).
| Sample Input 1 | Sample Output 1 |
|---|---|
3 0 1 2 |
0 1 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 7 8 9 |
10 15 22 |
