Knights P19852


Statement
 

pdf   zip

html

Given an n × m chess board, you can place on it as many black knights as you wish, as long as no two knights threaten each other. How many possibilities do you have?

For instance, these are just four of the 278 possibilities for n = 3 and m = 4:

boardfontsize=18pt showmover=false, label=false, maxfield=d3 showmover=false, label=false, maxfield=d3, setpieces=na3 showmover=false, label=false, maxfield=d3, setpieces=nc1,nc2,nb1 showmover=false, label=false, maxfield=d3, setpieces=na1,na3,nc3,nd3

Input

Input consists of several cases, each with n and m. Assume 1 ≤ n ≤ 4 and 1 ≤ m ≤ 1015.

Output

For every case, print the number of possibilities modulo 108 + 7.

Public test cases
  • Input

    1 1
    1 10
    2 1
    3 4
    4 2
    4 10
    4 1000000000000000
    

    Output

    2
    1024
    4
    278
    81
    18702843
    51397909
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Quinzè Concurs de Programació de la UPC - Final
    Date
    2017-09-13