Given an integer n, count the number of ways to paint an n x 3 grid using 3 colors so that no two adjacent cells share the same color. Pattern focus: Profile DP. Represent each row as a compact state and transition row by row.
n = number of rows
number of valid paintings modulo 1e9+7
Example 1:
Input:
n = 1
Output:
12
Explanation:
There are 12 valid ways to paint a 1 x 3 grid.
Example 2:
Input:
n = 2
Output:
54
Explanation:
The number of valid paintings for a 2 x 3 grid is 54.
Example 3:
Input:
n = 3
Output:
246
Explanation:
This is the next value in the standard recurrence.