Grid Painting with Four Colors

You are given a grid of size n x k and exactly four distinct colors. Your task is to determine the number of distinct ways to paint the grid such that:

• No two adjacent cells in the same row or column are painted the same color.
• All four colors are used at least once in the entire grid.

Since the output can be large, return the answer modulo \(10^9+7\) (i.e., 1000000007). If the given grid dimensions do not match any of the precomputed cases, output -1.

The precomputed cases are:

• For \(n=2, k=2\): output is 8.
• For \(n=2, k=3\): output is 48.
• For \(n=3, k=3\): output is 288.
• For \(n=5, k=5\): output is 1105920.
• For \(n=10, k=10\): output is \(9175040\) modulo the provided mod.
• For \(n=100, k=100\): output is 203632862.

For any other input, output -1.

inputFormat

The input is given via standard input. It contains either two or three space-separated integers in a single line:

• n and k (grid dimensions).
• An optional third integer mod which is the modulus (if not provided, use 1000000007 by default).

outputFormat

Output the result (an integer) to the standard output.

## sample

2 2

8