Domino rectangles P87164


Statement
 

pdf   zip

html

You have 4n identical 3-3 domino pieces, and you must cover with them a 3 × 3n rectangle. As you can see in the picture below, the positions (2, 2), (2, 5), …, (2, 3n − 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 ≤ 1012 and 2 ≤ m ≤ 106.

Output

For every case, print the number of 3 × 3n 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