Constrained Chessboard Coloring

You are given a chessboard of size $$n \times m$$. Each cell of the board must be colored either black or white (represented by 0 and 1 respectively). A coloring is considered valid if it satisfies the following two conditions.

• For every consecutive three cells (in a horizontal, vertical, or diagonal line) the colors are not all identical. Formally, for any triple of cells $$\{(x,y), (x+1,y), (x+2,y)\}, \quad \{(x,y), (x,y+1), (x,y+2)\},$$ $$\{(x,y), (x+1,y+1), (x+2,y+2)\},\quad \{(x,y), (x+1,y-1), (x+2,y-2)\}$$ (whenever all cells lie inside the board), it is not the case that all three cells have the same color.
• For every consecutive four cells (again, in any horizontal, vertical, or diagonal direction) it is forbidden that at least three of them are of the same color. In other words, for any four consecutive cells $$\{(x,y), (x+1,y), (x+2,y), (x+3,y)\}, \quad \{(x,y), (x,y+1), (x,y+2), (x,y+3)\},$$ $$\{(x,y), (x+1,y+1), (x+2,y+2), (x+3,y+3)\}, \quad \{(x,y), (x+1,y-1), (x+2,y-2), (x+3,y-3)\},$$ (if they are fully inside the board), neither color (0 or 1) appears three or more times in that block.

Your task is to count the number of valid colorings of the chessboard. Since the answer may be very large, output it modulo 1000000007.

inputFormat

The input consists of a single line containing two space‐separated integers $$n$$ and $$m$$ representing the number of rows and columns of the chessboard respectively.

For example:

2 3

outputFormat

Output a single integer, the number of valid colorings modulo 1000000007.

sample

1 1

2