a board of size m × n can choose any tile of size a × b such that there are no empty slots left. Request: Count the number of ways to pave the road in this case. Two ways of laying tiles are considered different each other if the number or arrangement of the bricks is different. Note that the two ways are opposites each other’s symmetry or rotation is considered different. Data Consists of a line containing two integers m, n separated by a space (1 m ≤ 10^5, 1 n ≤ 5) — degrees length and width of the path. Result Print a single integer that is the number of possible tiles. Since the result can be very large, you can simply print it out remainder when divided by 1 000 000 007 (10^9 + 7)

when n=1 then the answer will be 2^(m-1) I tried dynamic programming: for each added cell there will be 16 states that delete 1 of 4 edges or delete 2 opposite edges. but when I do, I still get infected. hope everyone can help me

input: 2 1 output: 2

input: 6 2 output: 2864

input: 3 3 output: 322