A triomino is a shape consisting of three squares joined via the edges. There are two basic forms:
If all possible orientations are taken into account there are six:
Any n by m grid for which n x m is divisible by 3 can be tiled with triominoes.
If we consider tilings that can be obtained by reflection or rotation from another tiling as different there are 41 ways a 2 by 9 grid can be tiled with triominoes:
In how many ways can a n by m grid be tiled in this way by triominoes? Print answer modulo ((10^9) + 7).
First line contains n and m.
Print one integer i.e. answer modulo 1000000007 = (10^9) + 7
1≤ n ≤ 6
1≤ m ≤ 21
n x m is divisible by 3
2 9
41