This problem is a programming version of Problem 117 from projecteuler.net
Using a combination of black square tiles and oblong tiles chosen from: red tiles measuring two units, green tiles measuring three units, and blue tiles measuring four units, it is possible to tile a row measuring five units in length in exactly fifteen different ways.
How many ways can a row measuring units in length be tiled?
As the answer can be extremely large, print it modulo .
Input Format
First line contains an integer denoting the number of test cases.
Each of the following lines contain one integer .
Constraints
Output Format
For each of test cases print one line containing a single integer - the answer to a problem modulo .
Sample Input
1
5
Sample Output
15