- All Contests
- ProjectEuler+
- Project Euler #117: Red, green, and blue tiles

# Project Euler #117: Red, green, and blue tiles

# Project Euler #117: Red, green, and blue tiles

_{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
```