Ways To Tile A Floor

Given a floor of dimensions 2 x N and tiles of dimensions 2 x 1, return the number of ways the floor can be tiled. A tile can either be placed horizontally i.e as a 1 x 2 tile or vertically i.e as 2 x 1 tile. Return the answer modulo 10⁹+7.

Input Format:

First Parameter - Number N.

Output Format:

Return the number

Example 1:

Input:
N = 3
Output:
3
Explanation:
We need 3 tiles to tile the board of size 2 x 3. 
We can tile in following 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.

Example 2:

Input:
N = 4
Output:
5
Explanation:
For a 2 x 4 board, there are 5 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.

Constraints:

• 1 <= N <= 10⁵
• Expected Time Complexity: O(N)
• Expected Auxiliary Space: O(1)