题目描述

一面仪式拼屏由 $2\times n$ 个单位正方形组成。工匠可以在相邻两列之间放置贯穿上下两行的金色竖缝；拼屏的左右边界也视为竖缝。所有竖缝把拼屏从左到右分成若干块矩形光板。每块光板的宽度必须是不超过 $m$ 的正整数。

一块宽度为 $a$ 的光板有上、下两条长度均为 $a$ 的灯带。一次点亮方案中，每条灯带都可以独立地整条点亮或不点亮。因此，这块光板可以贡献 $0$、$a$ 或 $2a$ 个被点亮的单位格。这里只关心被点亮的单位格总数，不把不同的点亮选择算作不同的拼屏方案。

考虑任意一条不是左边界的竖缝，以及这条竖缝左侧的所有完整光板。若这些光板的总宽度为 $s$，则这部分共有 $2s$ 个单位格。称这条竖缝是圆满的，当且仅当对于每个整数 $q$（$0\le q\le 2s$），都存在一种只使用这些完整光板的点亮方案，使恰好 $q$ 个单位格被点亮。

如果一组竖缝中的每一条非左边界竖缝（包括拼屏的右边界）都是圆满的，就称这组竖缝构成一个合法拼屏方案。

求合法拼屏方案的数量。两种方案不同，当且仅当它们至少有一条内部竖缝的位置不同。答案对 $1\,000\,000\,007$ 取模。

输入格式

从文件 mosaic.in 中读取数据。

输入一行两个整数 $n,m$，分别表示拼屏的宽度和每块光板允许的最大宽度。

输出格式

输出到文件 mosaic.out 中。

输出一个整数，表示合法拼屏方案数对 $1\,000\,000\,007$ 取模后的结果。

样例输入 #1

5 5

样例输出 #1

7

样例解释

从左到右写出各块光板的宽度，七种合法方案为

(1,1,1,1,1)
(1,1,1,2)
(1,1,2,1)
(1,2,1,1)
(1,2,2)
(1,1,3)
(1,3,1)

例如对于宽度序列 $(1,3,1)$，第一块光板可以得到 $0,1,2$ 个亮格；加入宽度为 $3$ 的第二块后，可以得到 $0$ 到 $8$ 的每个整数；再加入最后一块后，可以得到 $0$ 到 $10$ 的每个整数。

数据范围与约定

• $1\le m\le n\le 5\,000\,000$。
• 每块光板的宽度为正整数，不允许宽度为 $0$ 的光板。
• 内部竖缝只能位于两列之间；左右边界固定存在。
• 上、下灯带可以独立选择。只点亮上灯带与只点亮下灯带都贡献相同的亮格数，但它们不会使同一组竖缝被重复计数。
• 输出是唯一的，采用标准整数文本比较；除空白字符外，输出必须与标准答案的唯一整数相同。

各子任务为独立计分的测试点组，只有通过该组全部测试点才能获得该组分数。子任务 $1$ 的约束范围包含于子任务 $3$；子任务 $2$ 与子任务 $1$、$3$ 不互相依赖；所有前三个子任务的输入都满足子任务 $4$ 的总约束。

下发文件

包含本题额外3组大数据的输入与输出文件。

下载三组测试数据，非真实测试数据