# Painting Fences

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

The idea is to use a recursive approach to find the total number of ways to paint the fences. Let us consider the two colors are black and white.

We have to think about two possibilities:

- If the last color was black, then:
- If the second last color was black too, then we can only use white this time. Otherwise, we can use any color this time.

- Otherwise, if the last color was white, then:
- If the last second color was black, then we can use any color this time. Otherwise, we can only use black.

In this approach, we are going to make a recursive function **countWays(N). **This function will return the total number of ways to paint **N** fences.

**Algorithm:**

- Set
**mod**as**1000000007.** - Make a recursive function
**countWays(N)**where the**N**is**N**fences.- The base condition of this function is if
**N**is less than or equal to**1,**then return**2.** - Set
**result1**as the value returned from**countWays(N-1).** - Set
**result2**as the value returned from**countWays(N-2).** - Return the sum of
**result1**and**result2.**We will take modulo of this sum with**mod**as it can overflow.

- The base condition of this function is if

As discussed in the previous approach, we are using a recursive approach to find the total number of ways to paint the fences. In this approach, we will use memoization to reduce our time complexity by storing the solutions in the dynamic array. We have to maintain an array **dpArray **of size **N+1.** If we had already calculated the ways for a particular value of **N **then we can return **dpArray[N] **in that case instead of calculating the total number of ways again.

**Algorithm:**

- Set
**mod**as**1000000007.** - Make a recursive function
**findWays(N,dpArray)**where the**N**is**dpArray**is the memoization array. This function returns the number of ways to paint the**N**fences.- The base condition of this function is if
**N**is less than or equal to**1**- We will return
**2.**

- We will return
- Check If
**dpArray[N]**is not equal to**-1**.- We will return
**dpArray[N].**

- We will return
- Set
**result1**as the value returned from**findWays(N-1, dpArray).** - Set
**result2**as the value returned from**findWays(N-2, dpArray).** - Set
**dpArray[N]**as the sum of**result1**and**result2.**We will take modulo of this sum with**mod**as it can overflow. **Return dpArray[N].**

- The base condition of this function is if
- Make a function
**countWays(N)**where the**N**is**.**This function returns the number of ways to paint the**N**fences. **Make a dpArray of size N+1 and initialize all its elements with -1.**- Return the value returned by function
**findWays(N, dpArray).**

We will maintain two variables **prev** and **curr,** to find the total number of ways to paint the fences. We will initialize **prev** and **curr** as 2. We will traverse **ind **from 2 to **N**.

- We will find the number of ways to paint
**ind**fences, which is equal to the sum of**curr**and**prev**. We will set**temp**as the sum of**curr**and**prev**. - We will update the variable
**prev**as**curr**and**curr**as**temp**.

In the end, the variable **curr **stores the number of ways to paint **N** fences. We will return the variable **curr**.

**Algorithm:**

- Set
**mod**as**1000000007.** - Make a function
**countWays(N)**where the**N**is**N**fences.- Set
**curr**as**2.** - Set
**prev**as**2.** - Iterate
**ind**from**2**to**N.**- Set
**temp**as the sum of**curr**and**prev.**We will take modulo of this sum with**mod**as the sum can overflow. - Set
**prev**as**curr**. - Set
**curr**as**temp.**

- Set
- Return
**curr,**which is our required number of ways to paint**N**fences**.**

- Set