题目描述

题目译自 Romanian Master of Informatics 2021 Day2 T1 「NoM」

马塞尔最近开始了一种新的爱好：创建禅意花园。他很快发展了自己的风格，使用 $2 N$ 块石头作为花园特色。其中一半的石头是绿色的（覆盖着苔藓），并从 $1$ 到 $N$ 唯一编号，而另一半是灰色的（没有苔藓生长在上面），同样从 $1$ 到 $N$ 唯一编号。为了创建一个花园，马塞尔将拿起石头，并按照某种顺序将它们放在一条直线上，确保任何两块连续石头之间的距离恰好是 $1$ 英寸。

在判断花园的美感方面，所有花园都被认为是美丽的。然而，马塞尔关于他的花园有一个迷信：如果存在两块刻有相同数字的石头，并且它们之间的距离是 $M$ 英寸的倍数，那么花园就被认为是 $M$-不幸的，给创造那个花园的人带来巨大的不幸和 Code::Blocks 崩溃。马塞尔永远不会创造这样的花园。当然，所有其他花园都被认为是 $M$-幸运的。

作为他达到启蒙之旅的一部分，马塞尔已经开始创造所有可以创建的 $M$-幸运花园。然而，由于他也是一个深思熟虑且组织良好的个人，马塞尔希望在他开始旅程之前知道有多少个由 $2 N$ 块石头组成的 $M$-幸运花园。如果存在一个整数 $i\ (1 \leq i \leq 2 N)$，满足以下任意一个条件：

• 花园 $A$ 中第 $i$ 块石头的颜色与花园 $B$ 中第 $i$ 块石头的颜色不同
• 花园 $A$ 中第 $i$ 块石头上的数字与花园 $B$ 中第 $i$ 块石头上的数字不同。

则两个花园 $A$ 和 $B$ 被认为是不同的。

输入格式

输入包含一行两个整数 $N$ 和 $M$，表示马塞尔将创建由 $2 N$ 块石头组成的 $M$-幸运花园。

输出格式

在一行上，输出包含 $2 N$ 块石头的 $M$-幸运花园的数量对 $10^{9}+7$ 取模的结果。

100 23

171243255

1 1

0

在第二个样例中，可以创建两个花园。然而，没有花园是 $1$-幸运的，因为对于两个花园，编号为 $1$ 的石头之间的距离都是 $1$ 英寸，这是 $M=1$ 英寸的倍数。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq M \leq N \leq 2000$

详细子任务附加限制及分值如下表所示。