Submit solution

Points:
20 (partial)

Time limit:
1.4s

Memory limit:
256M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

For his gift, Inaho got a grid of square cells, initially all white. He wants to colour exactly cells black such that no two black cells are adjacent. Two cells are adjacent if they share a common side (so two cells which share only a corner are not adjacent). Output the number of ways to do this modulo .

#### Constraints

- In test cases worth 25% of points, .
- In test cases worth 25% of points, .
- In test cases worth 50% of points, .

In all test cases, .

#### Input Specification

The first and only line of input will contain and separated by a space.

#### Output Specification

A single line containing the answer.

#### Sample Input 1

`1 2`

#### Sample Output 1

`6`

#### Sample Input 2

`3 3`

#### Sample Output 2

`215`

#### Sample Input 3

`420 50`

#### Sample Output 3

`763771419`

#### Sample Input 4

`2015 0`

#### Sample Output 4

`1`

## Comments