> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/number-of-ways-to-paint-n-3-grid.md).

# Number of Ways to Paint N × 3 Grid

You have a `grid` of size `n x 3` and you want to paint each cell of the grid with exactly one of the three colours: **Red**, **Yellow** or **Green** while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).

You are given `n` the number of rows of the grid.

Return *the number of ways* you can paint this `grid`. As the answer may grow large, the answer **must be** computed modulo `10^9 + 7`.

**Example 1:**

```
Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown:
```

![](/files/-M9ITXhowmJbzgYIPQWr)

**Example 2:**

```
Input: n = 2
Output: 54
```

**Example 3:**

```
Input: n = 3
Output: 246
```

**Example 4:**

```
Input: n = 7
Output: 106494
```

**Example 5:**

```
Input: n = 5000
Output: 30228214
```

**Constraints:**

* `n == grid.length`
* `grid[i].length == 3`
* `1 <= n <= 5000`

**Explaination:**

1. There are only two possibilities to form a non-adjacent row: **3 colors combination** (use all three colors, e.g., RYG) and **2 color combination** (use only two of three colors, e.g., RYR).
2. We add the new row one by one. Apart from its inner adjacent relation, **every new added row only relies on the previous one row** (new added row is only adjacent with the row above it).
3. **Every color combination follows the same pattern indicated below**. 3-color combination can generate **two** 3-color combination, and **two** 2-color combination for the next round. 2-color combination can generate **two** 3-color combination, and **three** 2-color combination for the next round.

![](https://assets.leetcode.com/users/frankkkkk/image_1586662749.png)

Let's try to have a math eqution to show the change above.\
The number of 3-color combination for round n is: **S(n)**. The number of 2-color combination for round n is **T(n**).\
Thus, we can have two simple math equations reflecting the relation between current round (n) with next round (n + 1) for both 3-color-combination and 2-color-combination.

**S(n + 1) = 2 \* S(n) + 2 \* T(n)**\
**T(n + 1) = 2 \* S(n) + 3 \* T(n)**

```java
class Solution {
    public int numOfWays(int n) {
        int MOD = (int) (1e9 + 7);
        long color3 = 6;
        long color2 = 6;

        for (int i = 2; i <= n; ++i) {
            long tempColor3 = color3;
            color3 = (2 * color3 + 2 * color2) % MOD;
            color2 = (2 * tempColor3 + 3 * color2) % MOD;
        }

        return (int) (color3 + color2) % MOD;
    }
}
```