Road of the King

## 题目描述 有一个 $n$ 个点的图，目前一条边都没有。 有一个人在 $1$ 号点要进行 $m$ 次移动，终点不必是 $1$ 号点，假设第 $i$ 次从 $u$ 移动到 $v$，那么在 $u$ 与 $v$ 之间连一条有向边。 问有多少种序列能满足：最终 $n$ 个点组成的图是一个强连通图。答案对 $10^9+7$ 取模。 #### 数据范围 $1 \leq n,m \leq 300$ ## 输入格式 > $n$$\ m$ 两个整数 $n,m$，用一个空格隔开。 ## 输出格式 > $ans$ 一个整数表示答案。

[problemUrl]: https://atcoder.jp/contests/cf16-final/tasks/codefestival_2016_final_f 高橋王国には $ N $ 個の町があり、それぞれの町には $ 1～N $ の番号が付けられています。 この国の王様である高橋くんは、$ N $ 個の町を $ M $ 日間かけて廻る出張を計画しています。計画では、町の列 $ c $ を決め、$ i\ (1≦i≦M) $ 日目には町 $ c_i $ へ行くことにしました。すなわち、$ i $ 日目には、今いる町から町 $ c_i $ へ移動します。ただし、今いる町が町 $ c_i $ であった場合は移動しません。高橋くんははじめ町 $ 1 $ にいるものとします。 困ったことに、この国には道路が $ 1 $ 本もありません。しかたがないので高橋くんは、道路を作りながら歩くことにしました。高橋くんが町 $ a $ から町 $ b $ へ移動すると、町 $ a $ から町 $ b $ への一方通行の道路ができます。 高橋くんは国民思いの王様なので、出張の最終日の目的地に着いた直後に「どの町からどの町へも、高橋くんが作った道路を辿ることによって移動することが出来る」という条件を満たすようにしたいと考えました。このような条件を満たす町の列 $ c $ は何通り考えられるでしょうか？

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

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

3 3

2

150 300

734286322

300 150

0

### 制約 - $ 2≦N≦300 $ - $ 1≦M≦300 $ ### Sample Explanation 1 下図のように、$ c\ =\ (2,3,1) $ または $ c\ =\ (3,2,1) $ のときのみ条件を満たし、$ c\ =\ (2,3,2) $ や $ c\ =\ (2,1,3) $ や $ c\ =\ (1,2,2) $ などは条件を満たしません。 !\[\](https://atcoder.jp/img/code-festival-2016-final/199a3fd8d2aed75750901a206c8b7e76.png)