3995. 天桥

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$ 取模。