Painting Fences Problem Statement

You are given ‘N’ fences. Your task is to compute the total number of ways to paint these fences using only 2 colors, such that no more than 2 adjacent fences have the same color.

Due to potentially large results, return the solution modulo 10^9 + 7.

Example:

Input:

N = 2

Output:

4

Explanation:

For N = 2, there are 4 valid ways to paint the fences: [0, 1], [1, 0], [1, 1], and [0, 0]. Thus, the answer is 4.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10^6
• Time Limit: 1 sec