Coloring a Rectangle 2

Time limit1sMemory limit512 MB

Summary

Count binary colorings of an N by M grid, N up to 1e18 and M at most 5, with no 2x2 block of a single color, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Matrix, Combinatorics, Bit manipulation
Solved: No attempts yet

Problem

You are given an $N \times M$ rectangle divided into unit squares. Write a program to count the ways to color it so that the following conditions hold.

Every cell must be colored either black or white.
There must be no $2 \times 2$ square whose four cells are all the same color.

A valid coloring when $N = 3$ , $M = 3$

An invalid coloring when $N = 3$ , $M = 3$

Given $N$ and $M$ , find the number of valid colorings of the $N \times M$ rectangle, modulo $1\,000\,000\,007$ .

Input

The first line contains $N$ ( $1 \le N \le 10^{18}$ ) and $M$ ( $1 \le M \le 5$ ).

Output

Print the number of valid colorings of the $N \times M$ rectangle modulo $1\,000\,000\,007$ on the first line.

Examples3

Example 1
Input
```
2 2
```
Expected output
```
14
```
Example 2
Input
```
3 3
```
Expected output
```
322
```
Example 3
Input
```
100 5
```
Expected output
```
264366292
```