0

Painting Fences

Difficulty: MEDIUM
Contributed By
Waris
Avg. time to solve
25 min
Success Rate
75%

Problem Statement

You are given ‘N’ fences. Your task is to find the total number of ways to paint fences using 2 colors only such that at most 2 adjacent fences are painted with the same color.

As the answer can be too large, return the answer modulo 10^9 + 7.

For Example:
Consider If N = 2, then there can be 4 different ways to color fences such that at most 2 adjacent fences have the same color-:
[ [0, 1],
  [1, 0],
  [1, 1],
  [0, 0] ]
Hence, the answer is 4.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’, representing the number of fences.
Output Format:
For each test case, print a single integer denoting the number of ways to paint the fences modulo 10^9 + 7.

Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^6

Time Limit: 1 sec
Sample Input 1:
2
2
3
Sample Output 1 :
4
6
Explanation:
For test case 1: 
In this case, N = 2, so the total number of ways to color fences using 2 colors is 4
[ [0, 0],
  [1, 1],
  [0, 1],
  [1, 0] ]
Hence, the answer is 4.

For test case 2: 
In this case, N = 3, so the total number of ways to color fences using 2 colors is 6.
[ [0, 1, 1],
  [1, 0, 0],
  [0, 1, 0],
  [1, 0, 1],
  [0, 0, 1],
  [1, 1, 0] ]
Hence, the answer is 6.
Sample Input 2:
2
4
5
Sample Output 2 :
10
16
Reset Code
Full screen
copy-code
Console