Now we start to describe a kind of directed graph called the Drying Rack Graph (DRG) with a parameter N.

A DRG contains N groups of vertexes. The i-th group contains 2N vertices: .

There are two types of edges in DRG: intra-group edges (edges inside each group) and inter-group edges (edges between groups).

Intra-Group Edge: For the i-th group, the following intra-group edges exist:

• , for all integer j such that ;
•  , for all integer j such that or .

Inter-Group Edge: The following inter-group edges exist:

• , for all integer i such that ;
• , for all integer i such that .

Now we want to know the number of topo-order of a DRG parameterized with N.

A topo-order of a directed graph G=(V, E) is a permutation of all vertices from V(G) such that for all i < j,

In order to avoid calculations of huge integers, report answer modulo a prime M instead.

The input contains only two integers N, M , and M is a prime.

Output one integer indicating the answer. 

2 1073741789

31

3 1073741789

7954100