S - マス目 Editorial /

Time Limit: 8 sec / Memory Limit: 256 MiB

Problem Statement

すぬけ君は、H x W のマス目を白と黒に塗り分けることにした。
  • 左上のマス目と右下のマス目は黒に塗る。
  • 左上のマス目から、黒いますを上下左右にたどって、右下のマス目に行くことができる。
条件を満たす塗り分け方の個数を mod 1,000,000,007 で求めよ。

Constraints

  • 2 ≤ H ≤ 6
  • 2 ≤ W ≤ 100

Input Format

入力は以下の形式で標準入力から与えられる。
H W

Output Format

答えを一行に出力せよ。

Sample Input 1

2 2

Sample Output 1

3
左上と右下が黒で、左下と右上のうち少なくとも一方が黒であるような塗り方が条件を満たす。

Sample Input 2

5 8

Sample Output 2

950397139