配点: 100 点
問題文
今天是平安夜。 PAKEN为平成时代的最后一个圣诞节制作了以下装饰品。
- 装饰品由“灯泡”和“棍子”组成。装饰品的制作方法如下。 创建一组满足
- 電球 (a, b) (0 \leq a \leq D, -a \leq b \leq a) 的整数。a 称为“深度”,b 称为“横坐标”。
- 電球 (0, 0) 和 按字典顺序比较 (1, -1) 和一个灯泡 直接用棍子绑 (0, 0) 和 按字典顺序比较 (1, 1) 。
- 同一深度处,横坐标为 1 直接用一根棍子连接仅不同的灯泡。 当
- 電球 (a, -(a-1)) 和 按字典顺序比较 (a+1, -(a+1)) 和一个灯泡 直接用棍子绑 (a, a-1) 和 按字典顺序比较 (a+1, a+1) 。
例如,D = 1, 2, 3 时,图形将如下图所示。

它看起来像一棵圣诞树。
PAKEN 你就是颜色
我想使用 1 减去 X 最多 X 颜色为所有灯泡着色。但与灯杆直接连接的灯泡颜色不宜相同。
有多少种着色方式?
小于或等于1 \ 000 \ 000 \ 007 请求出除以后的余数。
制約
- D 是 您也可以写 1 以上 10 \ 000 \ 000 的整数 给出了
- X 是 您也可以写 1 以上 1 \ 000 \ 000 \ 000 的整数 给出了
入力
输入是按以下格式从标准输入给出的。
D X
出力
有多少种着色方式? 小于或等于1 \ 000 \ 000 \ 007 后的余数打印在一行上。
小課題
小課題 1 [2 点]
输入满足以下条件。
- D = 1
- X \leq 4
小課題 2 [12 点]
输入满足以下条件。
- D \leq 2
- X \leq 6
小課題 3 [21 点]
输入满足以下条件。
- D \leq 4
- X \leq 7
小課題 4 [31 点]
输入满足以下条件。
- D \leq 50
- X \leq 25
小課題 5 [18 点]
- D \leq 50 很满意。
小課題 6 [11 点]
- D \leq 100 \ 000 很满意。
小課題 7 [5 点]
- 没有其他限制。
入力例 1
1 2
出力例 1
2
下面 2 绘画有不同的方法。
入力例 2
1 3
出力例 2
18
下面 18 绘画有不同的方法。

该输入是 1 约束。
入力例 3
4 5
出力例 3
101969466
该输入是 2 约束,但存在小问题 满足 3 约束。