GFSSOC '15 Winter S4 - Starry Nights - Olympiads Online Judge

GFSSOC '15 Winter S4 - Starry Nights

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 16M

Authors:

Problem type

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$ ~r~ and column $c$ ~c~, there should also be * characters at $(r+1, c-1)$ ~(r+1, c-1)~, $(r+1, c)$ ~(r+1, c)~, and $(r+1, c+1)$ ~(r+1, c+1)~. Furthermore, stars may not share * characters, that is, they CANNOT OVERLAP.

Invalid paintings are shown 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$ ~1\,000\,000\,007~ $(10^9 + 7)$ ~(10^9 + 7)~.

Input Specification

The first and only line of input will contain 2 integers $R$ ~R~ and $C$ ~C~, the height and width of the canvas.

Constraints

For all test cases, $2 \le R$ ~2 \le R~, $3 \le C$ ~3 \le C~.

Subtask 1 [20%]

$R \le 100, C \le 15$ ~R \le 100, C \le 15~

Subtask 2 [20%]

$R \le 50, C \le 22$ ~R \le 50, C \le 22~

Subtask 3 [60%]

$R \le 100, C \le 22$ ~R \le 100, C \le 22~

Output Specification

Output one integer, the number of ways ButaneBot can paint a starry night on a canvas of size $R$ ~R~ by $C$ ~C~.

Sample Input

2 6

Sample Output

Explanation for Sample Output

The 5 possible paintings are shown below:

~*~~~~        ~~*~~~        ~~~*~~        ~~~~*~        ~*~~*~
***~~~        ~***~~        ~~***~        ~~~***        ******

Comments

0

r3mark commented on Dec. 29, 2015, 5:21 p.m.

Would LLSLLLL LSSSSLL LLLSSSL be considered a starry night? (L's are the tildes and S's are the asterisks)

5
d commented on Dec. 29, 2015, 10:17 p.m.
~~*~~~~ ~****~~ ~~~***~

Yes, because the stars don't overlap each other.

7
bobhob314 commented on Dec. 29, 2015, 10:16 p.m. ← edited →
Edited for clarity.

~~*~~~~ ~****~~ ~~~***~