Tiling Problem Statement

Given a board with 2 rows and N columns, and an infinite supply of 2x1 tiles, determine the number of distinct ways to completely cover the board using these tiles.

You can place each tile:
1. Horizontally as a 1x2 tile
2. Vertically as a 2x1 tile

Input:

N

Output:

The number of ways to tile the board modulo 10^9 + 7

Example:

Input:

N = 4

Output:

5

Explanation:

The image shows an example of possible tile arrangements for a board size of N = 4. The board is completely covered using the available tiles in multiple distinct configurations.

Constraints:

1

Question

Tiling Problem Statement

Given a board with 2 rows and N columns, and an infinite supply of 2x1 tiles, determine the number of distinct ways to completely cover the board using these tiles.

You can place each tile:
1. Horizontally as a 1x2 tile
2. Vertically as a 2x1 tile

Input:

Output:

The number of ways to tile the board modulo 10^9 + 7

Example:

Input:

N = 4

Output:

Explanation:

The image shows an example of possible tile arrangements for a board size of N = 4. The board is completely covered using the available tiles in multiple distinct configurations.

Constraints:

1 <= N <= 10¹⁸
Time limit: 1 sec

Note:

You are not required to print the output explicitly, just implement the function as the printing is handled by the system.

Accepted Answer

Determine distinct ways to cover a 2-row N-column board using 2x1 tiles, either horizontally or vertically.

Dynamic Programming Approach: Use a recurrence relation to calculate the number of ways to tile the board.
Recurrence Relation: The number of ways to tile a 2xN board can be expressed as dp[n] = dp[n-1] + dp[n-2].
Base Cases: dp[1] = 1 (one vertical tile) and dp[2] = 2 (two vertical tiles or two horizontal tiles).
Matrix Exponentiation: For large N (up to 10^18), use matrix exponentiation to compute results efficiently.
Modulo Operation: Return the result modulo 10^9 + 7 to handle large numbers.