ButaneBot is a talented artist, and he spends most of his time painting. When he was still human Butane was not very knowledgeable in art, and only programmed himself to be able to paint
~ characters and
* characters. After many trials and experiments, ButaneBot found that the most beautiful paintings he made using these two characters were those of starry nights, and so now he only paints starry nights. A painting is a starry night if it contains at least one star and all its
* characters are used for stars.
A star is a pattern that looks exactly like this:
~*~ *** ~~~
To be more specific, if a star has its top
* at row ~r~ and column ~c~, there should also be
* characters at ~(r+1, c-1)~, ~(r+1, c)~, and ~(r+1, c+1)~. Furthermore, stars may not share
* characters, that is, they CANNOT OVERLAP.
Invalid paintings are show below:
~~~*~ ~~*** ~***~ ~~~~~ ~~*~~ ~***~ ~~~~~ ~~~~~ ~***~ ~~*~~ ~~*~~ ~***~ ~~~~~ ~~~~* ~~~~~
For the first painting, there are 2 overlapping stars, or rather 3 extra
* characters whichever way you look at it. The second painting includes an upside down star pattern, which is not valid. The third painting has a rogue
* character not used for stars.
Given the dimensions of the canvas ButaneBot would like to paint his starry night on, find how many unique ways Butane can make his starry night painting. Since this number may be very large, output the number modulo ~1\,000\,000\,007~ ~(10^9 + 7)~.
The first and only line of input will contain 2 integers ~R~ and ~C~, the height and width of the canvas.
For all test cases, ~ 3 \le C~, ~2 \le R~
Subtask 1 [20%]
~R \le 100, C \le 15~
Subtask 2 [20%]
~R \le 50, C \le 22~
Subtask 3 [60%]
~R \le 100, C \le 22~
Output one integer, the number of ways ButaneBot can paint a starry night on a canvas of size ~R~ by ~C~.
Explanation for Sample Output
The 5 possible paintings are shown below:
~*~~~~ ~~*~~~ ~~~*~~ ~~~~*~ ~*~~*~ ***~~~ ~***~~ ~~***~ ~~~*** ******