注意到当前移动到的位置并不重要，重要的是经过的点数和 \(1\) 所在强连通分量大小，因此把它们放进状态里：设 \(f_{i,j,k}\) 表示进行 \(i\) 次移动，经过了 \(j\) 个不同的点，此时 \(1\) 所在的强连通分量大小为 \(k\) 的方案数。
考察下一次移动到的点的情况：
- 没有访问过：共有 \(n-j\) 种此类点，且此时不在 \(1\) 所在强连通分量，因此有转移 \(f_{i+1,j+1,k}\gets f_{i,j,k}\times(n-j)\)。
- 访问过，不在 \(1\) 所在强连通分量：共有 \(j-k\) 种此类点，此时依然不在 \(1\) 所在强连通分量，因此有转移 \(f_{i+1,j,k}\gets f_{i,j,k}\times(j-k)\)。
- 访问过，且在 \(1\) 所在强连通分量：共有 \(k\) 种此类点，此时所有访问过的点都并入 \(1\) 所在强连通分量，因此有转移 \(f_{i+1,j,j}\gets f_{i,j,k}\times k\)。
时间复杂度 \(O(n^2m)\)。
// Problem: Road of the King
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_codefestival_2016_final_f
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
template<int mod>
inline unsigned int down(unsigned int x) {
return x < mod ? x : x - mod;
}
template<int mod>
struct Modint {
unsigned int x;
Modint() = default;
Modint(int x) : x(x) {}
friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
friend Modint operator^(Modint a, int k) {Modint ans = 1; for(; k; k >>= 1, a *= a) if(k & 1) ans *= a; return ans;}
friend Modint operator~(Modint a) {return a ^ (mod - 2);}
friend Modint operator/(Modint a, Modint b) {return a * ~b;}
friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
friend Modint& operator^=(Modint& a, int k) {return a = a ^ k;}
friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
friend Modint& operator++(Modint& a) {return a += 1;}
friend Modint operator++(Modint& a, int) {Modint b = a; ++a; return b;}
friend Modint& operator--(Modint& a) {return a -= 1;}
friend Modint operator--(Modint& a, int) {Modint b = a; --a; return b;}
friend Modint operator-(Modint a) {return a.x == 0 ? 0 : mod - a.x;}
friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};
typedef Modint<1000000007> mint;
const int N = 305;
int n, m;
mint dp[N][N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
dp[0][1][1] = 1;
rep(i, 0, m - 1) {
rep(j, 1, n) {
rep(k, 1, j) {
dp[i + 1][j + 1][k] += dp[i][j][k] * (n - j);
dp[i + 1][j][k] += dp[i][j][k] * (j - k);
dp[i + 1][j][j] += dp[i][j][k] * k;
}
}
}
cout << dp[m][n][n] << endl;
return 0;
}