分数: 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