# Tiling Problem

Posted: 25 Jul, 2020
Difficulty: Hard

## PROBLEM STATEMENT

#### You have been given a board where there are '2' rows and 'N' columns. You have an infinite supply of 2x1 tiles, and you can place a tile in the following ways:

``````1. Horizontally as 1x2 tile
2. Vertically as 2x1 tile
``````

#### Count the number of ways to tile the given board using the available tiles.

##### Note :
``````The number of ways might be large so output your answer modulo 10^9 + 7.
``````

#### Here an example of tile and board for 'N' = 4 :

##### Input format :
``````The first and only line of each test case contains an Integer 'N' which denotes the size of the board, i.e. '2' rows and 'N' columns.
``````
##### Output format :
``````For each test case, print the number of ways to tile the board modulo 10^9 + 7.
``````
##### Note:
``````You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
``````
##### Constraints :
``````1 <= N <= 10^18

Where 'N' is the number of columns in the board.

Time limit: 1 sec
``````