Donuts Orientation

G: Donuts Orientation

story

Homu-chan's recent boom is making sweets. It seems that he makes a lot of sweets and shares them with his friends. Homu-chan seems to be trying to make donuts this time.

There are many important things in making donuts. Not only the dough and seasoning, but also the decorations to make it look cute. Through repeated trial and error, it seems that Homu-chan's commitment to decoration has become enthusiastic. Homu-chan wants to make a lot of donuts because he wants many people to eat the donuts that he has been particular about.

By the way, it doesn't matter if you stick to it, but is it possible to prepare a sufficient number of donuts that Homu-chan is particular about?

problem

For integers N greater than or equal to 3, create a graph of 2N vertices as follows.

• Number each vertex from 1 to 2N.
• For each integer 1 \ leq a \ leq N, put an undirected edge between vertices 2a-1 and 2a.
• For each integer 1 \ leq b \ leq 2N-2, put an undirected edge between vertices b and b + 2.
• Extend an undirected edge between vertices 1 and 2N-1 and 2 and 2N

Make a directed graph by orienting each side of this graph. That is, if there is an undirected edge between the vertices u and v, make it a directed edge from u to v or a directed edge from v to u.

I would like to know how many directed graphs created in this way do not have a cycle. The answer is very large, so find the remainder after dividing by the prime number M.

Input format

N M

Constraint

• 3 \ leq N \ leq 1,000
• 10 ^ 8 \ leq M \ leq 10 ^ 9 + 7
• M is guaranteed to be prime

Output format

Output the remainder of dividing the number of directed graphs that satisfy the condition by M.

Input example 1

3 1000000007

Output example 1

204

Since N = 3, we make a graph with 6 vertices. An example of a directed graph that meets the conditions is as follows.

Due to the existence of cycles, the directed graph shown below does not meet the condition.

Input example 2

128 998244353

Output example 2

996915100

Note that the remainder after dividing by M is output.

Example

Input

3 1000000007

Output

204

inputFormat

Input format

N M

Constraint

• 3 \ leq N \ leq 1,000
• 10 ^ 8 \ leq M \ leq 10 ^ 9 + 7
• M is guaranteed to be prime

outputFormat

Output format

Output the remainder of dividing the number of directed graphs that satisfy the condition by M.

Input example 1

3 1000000007

Output example 1

204

Since N = 3, we make a graph with 6 vertices. An example of a directed graph that meets the conditions is as follows.

Due to the existence of cycles, the directed graph shown below does not meet the condition.

Input example 2

128 998244353

Output example 2

996915100

Note that the remainder after dividing by M is output.

Example

Input

3 1000000007

Output

204

样例

3 1000000007

204