题目描述

joisino お姉ちゃん有一个大箱子，以及许多红色积木和蓝色积木。joisino お姉ちゃん决定按照以下步骤，将这些积木堆起来。

首先，将红色积木和蓝色积木一共 $N$ 个放入箱子中。只要总数为 $N$，每种颜色的积木数量没有限制。特别地，其中一种颜色的积木数量为 $0$ 也可以。接下来，要进行 $M$ 次如下操作。一次操作分为以下三个步骤：

• 从箱子中拿出任意一个积木。
• 将一块红色积木和一块蓝色积木各放入箱子中。
• 再从箱子中拿出任意一个积木。

经过 $M$ 次操作后，把这 $2 \times M$ 个取出的积木按照取出的顺序依次叠起来。joisino お姉ちゃん很好奇，按照上述方式堆起来的 $2 \times M$ 个积木的颜色组合有多少种。你的任务是替 joisino お姉ちゃん编写一个程序来计算这个数量。由于答案可能非常大，请输出其对 $10^9+7$ 取模后的结果。

输入格式

输入将以下述格式从标准输入中给出。

$N$ $M$

输出格式

请输出可能的堆积积木颜色组合总数，对 $10^9+7$ 取模后的结果。

样例 1

输入

2 3

输出

56

样例 2

输入

1000 10

输出

1048576

样例 3

输入

1000 3000

输出

693347555

说明/提示

限制条件

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

样例解释 1

取出积木的步骤一共会执行 $6$ 次。仅有在第 $2,3,4,5$ 次取出的积木颜色全部相同时的取法是不可能的，因此答案是 $2^6 - 2 \times 2 \times 2 = 56$。

由 ChatGPT 5 翻译