Now that we have seen dynamic programming (and a simple tiling problem), it's time for a more challenging one. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let's get started!

# Problem Statement

Like before, we are given a grid of size n \times 2 and we need to count the number of ways in which we can tile the grid such that the entire grid is covered and no tiles overlap. However, now we have two types of tiles available, (a) tiles of size 2 \times 1 and (b) L-shaped tiles which cover three squares.

Note: Each type of tiles look identical to other tiles of the same type. Two ways of tiling are different based on which tiles are placed and in what orientation.

*Since the answer can be very large, output the answer modulo 1000003 (That is, the remainder the answer leaves when divided by 1000003. ).*

# Example

There are 5 possible ways of tiling a 3 \times 2 grid.

Tiling 1:Three vertical tiles__ __ __| | | ||__|__|__|Tiling 2:1 vertical tile, followed by 2 horizontal tiles__ _____| |_____||__|_____|Tiling 3:2 horizontal tiles, followed by 1 vertical tile_____ __|_____| ||_____|__|Tiling 4:2 L-shaped tiles._____ __| __| ||__|_____|Tiling 5:2 L-shaped tiles the other way.__ _____| |__ ||_____|__|

Note that it is legal to mix the two types of tiles. For example, the following are some examples of tiling a 4 \times 2 grid.

__ _____ __| |_____| ||_____|_____|__ _____ __| |__ | ||_____|__|__|

# IO description

**Input description:** The first line contains the number of test cases T. The test case is on a separate line, a single number n denoting the length of the grid.

**Sample input**:

423410

**Output description**: Output should contain T lines. Each line should contain the answers for the respective test case, the number of ways of tiling modulo 1000003.

**Sample output**:

25111255

# Submitting your solution

Once you are confident of your solution, run your code on the following input. Then take the quiz!

103102360269832159751892598776401

# Progressive 'hint-by-hint' solution

Only look at the hints if you can't solve the problem for **at-least 20-minutes**. Read **only one hint** that you could not figure out on your own. Then spend **at-least 20-minutes** trying to solve the problem again.

Hint 1 (dynamic programming state):

Hint 2:

Hint 3 (recursion):

Hint 4:

Hint 5:

# Full solution

The solution for this assignment is included at the end of the quiz. The code executes within 0.00 seconds.

If we used naive recursion, the solution's execution time would be way more than our lifetimes!