New Year's '15 P6 - Tiles

View as PDF

Submit solution

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

Author:
Problem type

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.

Constraints

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

In all test cases, 0 \le M \le 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

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

There are no comments at the moment.