Josh felt bored during his lessons, so he took out some pennies, laid of them in a row and stacked the coins such that each coin rests on other coins. He began wondering how many ways could you stack pennies on top of each other if there are pennies on the bottom row. Josh couldn't figure it out so he passed the problem to you.
Given queries, output the number of ways to stack pennies if there were pennies on the bottom row. Output the answer modulo .
The first list of input will contain an integer , the number of queries.
The next lines will contain a single integer , the number of pennies on the bottom row.
Output lines, the number of ways to stack the pennies modulo .
3 2 3 20
2 5 564120378
When , there are ways to place the pennies. The picture below are those five ways.