Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

# Tiling Problem

Hard
0/120
Average time to solve is 45m
Contributed by

## 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 :

Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= N <= 10^18

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

Time limit: 1 sec
``````
##### Sample Input 1 :
``````3
``````
##### Sample Output 1 :
``````3
``````
##### Explanation to Sample Input 1 :
``````For a 2*3 board, there are three ways:
1. Place all 3 tiles vertically.
2. Place first tile vertically and remaining 2 tiles horizontally.
3. Place first 2 tiles horizontally and remaining tiles vertically.
``````
##### Sample Input 2 :
``````4
``````
##### Sample Output 2 :
``````5
``````
##### Explanation to Sample Input 2 :
``````For a 2*4 board, there are five ways:
1. All 4 vertical
2. All 4 horizontal
3. First 2 vertical, remaining 2 horizontal
4. First 2 horizontal, remaining 2 vertical
5. Corner 2 vertical, middle 2 horizontal
``````
Console