Submit solution

Points: 20 (partial)
Time limit: 1.4s
Memory limit: 256M

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 5 \times N grid of square cells, initially all white. He wants to colour exactly M 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 10^9+7.


  • In test cases worth 25% of points, 1 \leq N \leq 6.
  • In test cases worth 25% of points, 7 \leq N \leq 10\,000.
  • In test cases worth 50% of points, 10^8 \leq N \leq 10^9.

In all test cases, 0 \leq M \leq 50.

Input Specification

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

Output Specification

A single line containing the answer.

Sample Input 1

1 2

Sample Output 1


Sample Input 2

3 3

Sample Output 2


Sample Input 3

420 50

Sample Output 3


Sample Input 4

2015 0

Sample Output 4



There are no comments at the moment.