配点 : $1000$ 点

問題文

高橋王国には $N$ 個の町があり、それぞれの町には $1 \sim N$ の番号が付けられています。

この国の王様である高橋くんは、$N$ 個の町を $M$ 日間かけて廻る出張を計画しています。計画では、町の列 $c$ を決め、$i (1 \leq i \leq M)$ 日目には町 $c_i$ へ行くことにしました。すなわち、$i$ 日目には、今いる町から町 $c_i$ へ移動します。ただし、今いる町が町 $c_i$ であった場合は移動しません。高橋くんははじめ町 $1$ にいるものとします。

困ったことに、この国には道路が $1$ 本もありません。しかたがないので高橋くんは、道路を作りながら歩くことにしました。高橋くんが町 $a$ から町 $b$ へ移動すると、町 $a$ から町 $b$ への一方通行の道路ができます。

高橋くんは国民思いの王様なので、出張の最終日の目的地に着いた直後に「どの町からどの町へも、高橋くんが作った道路を辿ることによって移動することが出来る」という条件を満たすようにしたいと考えました。このような条件を満たす町の列 $c$ は何通り考えられるでしょうか？

制約

• $2 \leq N \leq 300$
• $1 \leq M \leq 300$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

出力

答えを $1000000007 (=10^9+7)$ で割った余りを出力せよ。

3 3

2

下図のように、$c = (2,3,1)$ または $c = (3,2,1)$ のときのみ条件を満たし、$c = (2,3,2)$ や $c = (2,1,3)$ や $c = (1,2,2)$ などは条件を満たしません。

150 300

734286322

300 150

0