单点时限: 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$ 是偶数。
输出一行表示答案。
4 2
6
不妨用字母 a 和 b 分别代表两种颜色。则 $6$ 种方案分别为：aaaa、aabb、abba、baab、bbaa、bbbb。