1232. Number of Ways to Paint N x 3 Grid

You paint an n x 3 grid using red, yellow, and green so that no two adjacent cells (sharing a side) have the same color. Return the number of valid colorings modulo 1000000007. The input is JSON {n}.

Input: JSON {n}.

Output: Integer — the number of colorings modulo 1e9+7.

Examples

Input: {"n":1}
Output: 12
Explanation: Twelve valid single rows.

Input: {"n":2}
Output: 54
Explanation: Fifty-four valid two-row grids.

Input: {"n":5000}
Output: 30228214
Explanation: Large n modulo 1e9+7.

Constraints

• 1<=n<=5000

Asked by