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 .
First line contains an integer denoting the number of test cases.
Each of the following lines contain one integer .
For each of test cases print one line containing a single integer - the answer to a problem modulo .