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

Method:

https://media.geeksforgeeks.org/wp-content/uploads/final1.v1.png

Solution:

Time: O(n)
Space: O(1)

public class Solution {
    public int solve(int A) {
        int MOD = (int) 1e9 + 7;
        long color3 = 24;
        long color2 = 12;
        for (int i = 2; i <= A; i ++) {
            long prevColor3 = color3;
            color3 = (11 * color3 + 10 * color2) % MOD;
            color2 = (5 * prevColor3 + 7 * color2) % MOD;
        }
        return (int) ((color3 + color2) % MOD);
    }
}