A Stack Problem

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M
Python 128M

Problem type

NOTICE: Data has been altered on 21/12/2019, increasing constraints of Q and N.

Josh felt bored during his lessons, so he took out some pennies, laid N (0 \le N \le 10^6) of them in a row and stacked the coins such that each coin rests on 2 other coins. He began wondering how many ways could you stack pennies on top of each other if there are N pennies on the bottom row. Josh couldn't figure it out so he passed the problem to you.

Given Q (1 \le Q \le 10^5) queries, output the number of ways to stack pennies if there were N pennies on the bottom row. Output the answer modulo 10^9+7.

Input Specification

The first list of input will contain an integer Q (1 \le Q \le 10^5), the number of queries.

The next Q lines will contain a single integer N (0 \le N \le 10^6), the number of pennies on the bottom row.

Output Specification

Output Q lines, the number of ways to stack the pennies modulo 10^9+7.

Sample Input


Sample Output



When N = 3, there are 5 ways to place the pennies. The picture below are those five ways.



There are no comments at the moment.