0

# Painting Fences

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

Problem Statement

#### 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] ]
``````
##### 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] ]

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] ]
``````2
``````10