You have 4*n* identical 3-3 domino pieces,
and you must cover with them a 3 × 3*n* rectangle.
As you can see in the picture below,
the positions (2, 2), (2, 5), …, (2, 3*n* − 1) of the rectangle
must be left empty.
Depending on *n*, how many different rectangles are possible?

For instance,
these are the two only possible rectangles for *n* = 1,
two of the six possible rectangles for *n* = 2,
and a possible rectangle for *n* = 7:

**Input**

Input consists of several cases,
each with two integer numbers *n* and *m*.
You can assume 0 ≤ *n* ≤ 10^{12} and 2 ≤ *m* ≤ 10^{6}.

**Output**

For every case,
print the number of 3 × 3*n* rectangles modulo *m*.

Public test cases

**Input**

0 1000 1 1000 2 1000 2 4 7 127 1000000000000 998877

**Output**

1 2 6 2 61 751275

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Cinquè Concurs de Programació de la UPC - Final
- Date
- 2007-10-03