/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 900 点
問題文
joisinoお姉ちゃんは、大きな箱と、たくさんの赤い積み木と青い積み木を持っています。 joisinoお姉ちゃんは、次の手順にそって、これらの積み木を積み上げることにしました。
まず、赤い積み木と青い積み木を、合わせて N 個、箱に入れます。 合計で N 個ならば、それぞれの色の積み木の個数に制限はありません。 特に、一方の色の積み木の個数が 0 個でも構いません。 次に、ある操作を M 回行います。 1 回の操作は、以下の 3 つのステップからなります。
- 好きな積み木を箱から 1 つ取り出す。
- 赤い積み木と青い積み木を 1 つずつ箱にいれる。
- 再び、好きな積み木を箱から 1 つ取り出す。
M 回の操作のあと、それまでに取り出した積み木を、取り出した順番に積み重ねます。 joisinoお姉ちゃんは、こうして積みあがる 2 \times M 個の積み木の色の組み合わせが何通りあるか知りたくなりました。 あなたの仕事は、joisinoお姉ちゃんの代わりにこれを求めるプログラムを作ることです。 なお、答えは非常に大きくなることがあるので、10^9+7 で割った余りを出力してください。
制約
- 1 \leq N \leq 3000
- 1 \leq M \leq 3000
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
積み上がる積み木の色の組み合わせが何通りあるかを求め、10^9+7 で割った余りを出力せよ。
入力例 1
2 3
出力例 1
56
積み木を取り出すステップは合計で 6 回行われます。 2,3,4,5 番目に取り出す積み木の色が全て同じになるような取り出し方だけがあり得ないので、 答えは、2^6 - 2 \times 2 \times 2 = 56 となります。
入力例 2
1000 10
出力例 2
1048576
入力例 3
1000 3000
出力例 3
693347555
Score : 900 points
Problem Statement
Joisino has a lot of red and blue bricks and a large box. She will build a tower of these bricks in the following manner.
First, she will pick a total of N bricks and put them into the box. Here, there may be any number of bricks of each color in the box, as long as there are N bricks in total. Particularly, there may be zero red bricks or zero blue bricks. Then, she will repeat an operation M times, which consists of the following three steps:
- Take out an arbitrary brick from the box.
- Put one red brick and one blue brick into the box.
- Take out another arbitrary brick from the box.
After the M operations, Joisino will build a tower by stacking the 2 \times M bricks removed from the box, in the order they are taken out. She is interested in the following question: how many different sequences of colors of these 2 \times M bricks are possible? Write a program to find the answer. Since it can be extremely large, print the count modulo 10^9+7.
Constraints
- 1 \leq N \leq 3000
- 1 \leq M \leq 3000
Input
Input is given from Standard Input in the following format:
N M
Output
Print the count of the different possible sequences of colors of 2 \times M bricks that will be stacked, modulo 10^9+7.
Sample Input 1
2 3
Sample Output 1
56
A total of six bricks will be removed from the box. The only impossible sequences of colors of these bricks are the ones where the colors of the second, third, fourth and fifth bricks are all the same. Therefore, there are 2^6 - 2 \times 2 \times 2 = 56 possible sequences of colors.
Sample Input 2
1000 10
Sample Output 2
1048576
Sample Input 3
1000 3000
Sample Output 3
693347555