3995. 天桥

单点时限: 1.0 sec

内存限制: 512 MB

ECNU 有一条路,叫作「未曾设想的道路」,这条路上有 $n$ 朵云排成一排,那是五彩斑斓的白,与阳光交相辉映。Cuber QQ 和 Little Fang 想要在这条路上,搭起一座座天桥。

一座天桥以两朵云支撑。Cuber QQ 和 Little Fang 用二元组 $(x,y)$($x < y$) 表示以第 $x$ 朵云和第 $y$ 朵云为支撑的天桥。

为了饱满而不拥挤,Cuber QQ 和 Little Fang 希望每朵云都有且仅有一个天桥被它支撑。

为了美观而不凌乱,Cuber QQ 和 Little Fang 希望每座天桥两端的云朵具有相同的颜色,即第 $i$ 朵云的颜色是 $a_i$,那么 $a_x=a_y$。

为了协调而不突兀,Cuber QQ 和 Little Fang 希望天桥不会交叉。Cuber QQ 和 Little Fang 认为两个天桥 $(u,v)$ 和 $(x,y)$ 交叉当且仅当 $u<x<v<y$ 或者 $x<u<y<v$。

Cuber QQ 和 Little Fang 预见到了种种不同的天桥,因此他们希望你回答,若用 $k$ 种颜色给 $n$ 朵云染色,有多少染色方案使得「未曾设想的道路」能够按照 Cuber QQ 和 Little Fang 的要求搭天桥。

Cuber QQ 曰:你若想到了,回答了,多多少少能借这一契机,窥探缘分的去往。

Little Fang 曰:答案对 $10^9+7$ 取模。

输入格式

第一行两个正整数 $n,k$($1\le n,k\le 3000$),保证 $n$ 是偶数。

输出格式

输出一行表示答案。

样例

Input
4 2
Output
6

提示

不妨用字母 ab 分别代表两种颜色。则 $6$ 种方案分别为:aaaaaabbabbabaabbbaabbbb

39 人解决,75 人已尝试。

45 份提交通过,共有 218 份提交。

5.4 EMB 奖励。

创建: 4 月,3 周前.

修改: 4 月,3 周前.

最后提交: 1 月,1 周前.

来源: EOJ Monthly 2020.11

题目标签