#P18748. [正睿NOI2021训练] 纸带

[正睿NOI2021训练] 纸带

纸带

有一条宽为 22、长为 nn 的纸带,将其首尾相接拼成一个环。

使用若干边长为正整数、面积不超过 33 的小矩形,不重不漏地覆盖纸带外侧。每个小矩形染上 KK 种颜色中的一种,要求:

  1. 外侧任意一点都恰好被一块小矩形覆盖,覆盖在边界处按通常铺砖方式理解。
  2. 小矩形的任何部分都不能超出纸带外侧。
  3. 任意四块小矩形没有公共点。
  4. 任意两块有公共边段的小矩形颜色不同。
  5. 小矩形不能绕环一周后与自己形成公共边;特别地,n≤3n\le3 时,不允许一块小矩形沿长度方向覆盖整个圆周。

每块矩形只能横放或竖放。允许矩形跨越纸带首尾接缝。

求本质不同的带颜色覆盖方案数。两种方案当且仅当通过环的旋转可以重合时视为相同;颜色的名称固定,不能交换颜色。对 109+710^9+7 取模。

输入格式

一行两个正整数 n,Kn,K。

输出格式

一个整数,表示本质不同方案数模 109+710^9+7 的结果。

数据范围

1≤n,K≤1091\le n,K\le10^9。

样例 1

输入

2 3

输出

9

样例 2

输入

30 3

输出

363308443