AT_pakencamp_2018_day2_e クリスマスツリー　(Tree Coloring)

今天是平安夜。为了庆祝平成的最后一个圣诞节，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 君打算用 $ X $ 种不同的颜色（从颜色 1 到颜色 $ X $）给每个灯泡上色。要求是，任何直接连接的两个灯泡不得用相同的颜色。 你需要计算出总共有多少种不同的上色方法，并输出其除以 $ 1\ 000\ 000\ 007 $ 的余数。

输入由两部分组成，通过标准输入提供： > $ D $ $ X $

输出一行，表示在 $ 1\ 000\ 000\ 007 $ 取余后的上色方法数量。

### 约束条件 - $ D $ 是介于 $ 1 $ 和 $ 10\ 000\ 000 $ 之间的整数 - $ X $ 是介于 $ 1 $ 和 $ 1\ 000\ 000\ 000 $ 之间的整数 ### 子任务 子任务 $ 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 存在 $ 2 $ 种不同的涂色方式：  ### 样例解释 2 存在 $ 18 $ 种不同的涂色方式：  这个输入满足子任务 $ 1 $ 的约束条件。 ### 样例解释 3 这个输入不满足子任务 $ 2 $ 的约束条件，但满足子任务 $ 3 $ 的约束条件。 **本翻译由 AI 自动生成**