/ 
Time Limit: 3 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
高橋王国には N 個の町があり、それぞれの町には 1～N の番号が付けられています。
この国の王様である高橋くんは、N 個の町を M 日間かけて廻る出張を計画しています。計画では、町の列 c を決め、i (1≦i≦M) 日目には町 c_i へ行くことにしました。すなわち、i 日目には、今いる町から町 c_i へ移動します。ただし、今いる町が町 c_i であった場合は移動しません。高橋くんははじめ町 1 にいるものとします。
困ったことに、この国には道路が 1 本もありません。しかたがないので高橋くんは、道路を作りながら歩くことにしました。高橋くんが町 a から町 b へ移動すると、町 a から町 b への一方通行の道路ができます。
高橋くんは国民思いの王様なので、出張の最終日の目的地に着いた直後に「どの町からどの町へも、高橋くんが作った道路を辿ることによって移動することが出来る」という条件を満たすようにしたいと考えました。このような条件を満たす町の列 c は何通り考えられるでしょうか？
制約
- 2≦N≦300
- 1≦M≦300
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを 1000000007 (=10^9+7) で割った余りを出力せよ。
入力例 1
3 3
出力例 1
2
下図のように、c = (2,3,1) または c = (3,2,1) のときのみ条件を満たし、c = (2,3,2) や c = (2,1,3) や c = (1,2,2) などは条件を満たしません。
入力例 2
150 300
出力例 2
734286322
入力例 3
300 150
出力例 3
0
Score : 1000 points
Problem Statement
There are N towns in Takahashi Kingdom. They are conveniently numbered 1 through N.
Takahashi the king is planning to go on a tour of inspection for M days. He will determine a sequence of towns c, and visit town c_i on the i-th day. That is, on the i-th day, he will travel from his current location to town c_i. If he is already at town c_i, he will stay at that town. His location just before the beginning of the tour is town 1, the capital. The tour ends at town c_M, without getting back to the capital.
The problem is that there is no paved road in this kingdom. He decided to resolve this issue by paving the road himself while traveling. When he travels from town a to town b, there will be a newly paved one-way road from town a to town b.
Since he cares for his people, he wants the following condition to be satisfied after his tour is over: "it is possible to travel from any town to any other town by traversing roads paved by him". How many sequences of towns c satisfy this condition?
Constraints
- 2≦N≦300
- 1≦M≦300
Input
The input is given from Standard Input in the following format:
N M
Output
Print the number of sequences of towns satisfying the condition, modulo 1000000007 (=10^9+7).
Sample Input 1
3 3
Sample Output 1
2
As shown below, the condition is satisfied only when c = (2,3,1) or c = (3,2,1). Sequences such as c = (2,3,2), c = (2,1,3), c = (1,2,2) do not satisfy the condition.
Sample Input 2
150 300
Sample Output 2
734286322
Sample Input 3
300 150
Sample Output 3
0