← 返回题目列表

AtCoder · agc013_d

D. 堆积

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

Joisino 有很多红砖和蓝砖以及一个大盒子。 她将按照以下方式用这些砖块建造一座塔。

首先,她总共会选择 N 砖块并将其放入盒子中。 这里,盒子里每种颜色的砖块可以有任意数量,只要有 总共 N 砖块。 特别地,可以有零个红砖或零个蓝砖。 然后,她会重复一个手术 M 次,包括以下三个步骤:

  • 从盒子里取出任意一块砖块。
  • 将一块红砖和一块蓝砖放入盒子中。
  • 从盒子里取出另一块任意砖块。

之后 M 行动中,Joisino将通过堆叠来建造一座塔 2 \times M 从盒子中取出的砖块,按照取出的顺序排列。 她对以下问题感兴趣:这些有多少种不同的颜色序列 2 \times M 砖头可以吗? 编写一个程序来寻找答案。 由于它可能非常大,因此打印计数模数 10^9+7.

约束

  • 1 \leq N \leq 3000
  • 1 \leq M \leq 3000

输入

输入由标准输入按以下格式给出:

N M

输出

打印不同可能的颜色序列的计数 2 \times M 将堆叠的砖块,模数 10^9+7.


示例输入 1

2 3

示例输出 1

56

总共六块砖块将从盒子中取出。这些砖块唯一不可能的颜色序列是第二、第三、第四和第五块砖的颜色都相同的顺序。因此,有 2^6 - 2 \times 2 \times 2 = 56 可能的颜色序列。


示例输入 2

1000 10

示例输出 2

1048576

示例输入 3

1000 3000

示例输出 3

693347555