> 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/ways-to-color-a-3xn-board.md).

# Ways to color a 3xN Board

Given a **3 x A** board, find the number of ways to color it using at most **4** colors such that no **2** adjacent boxes have same color.

Diagonal neighbors are not treated as adjacent boxes.

Return the ways modulo **109 + 7** as the answer grows quickly.

**Input Format:**

```
The first and the only argument contains an integer, A.
```

**Output Format:**

```
Return an integer representing the number of ways to color the board.
```

**Constraints:**

```
1 <= A < 100000
```

**Examples:**

```
Input 1:
    A = 1

Output 1:
    36

Input 2:
    A = 2

Output 2:
    588
```

```java
public class Solution {
    public int solve(int A) {
        long color3 = 24;
        long color2 = 12;

        for (int i = 2; i <= A; i++) {
            long temp = color3;
            color3 = (11 * color3 + 10 * color2) % 1000000007;
            color2 = (5 * temp + 7 * color2) % 1000000007;
        }
        long ans = (color2 + color3) % 1000000007;

        return (int) ans;
    }
}
```