CYK's very fun graph building game

You build a graph on $N$ vertices. Number the vertices $1$ through $N$ and paint each one with one of $K$ colors. Any coloring is allowed.

Once the colors are fixed, you add edges. The edges must follow two rules.

• If $1 \le j < i \le N$ and vertex $i$ and vertex $j$ have different colors, you may add an edge from $i$ to $j$. You may also leave it out.
• Every vertex $i$ with $2 \le i \le N$ has at most one outgoing edge, so the out-degree of vertex $i$ is never more than $1$.

Vertex $1$ has no vertex with a smaller number, so it can never have an outgoing edge.

Two graphs are the same when every vertex carries the same color in both and the two edge sets are equal. For example, with $N = 3$ and $K = 2$ there are 24 different graphs, shown below.

Given $N$ and $K$, find the number of different graphs modulo 1,000,000,007.

The first line contains the number of vertices $N$ ($1 \le N \le 100$) and the number of available colors $K$ ($1 \le K \le 3$), separated by a single space.

Print the number of different graphs modulo 1,000,000,007 on one line.