Problem:
 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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul
from functools import lru_cache
from pprint import pprint

mod = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


n, m = LI()
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[1][1] = 1
for _ in range(m):
    new_dp = [[0] * (n + 1) for _ in range(n + 1)]
    for j in range(1, n + 1):
        for k in range(1, j + 1):
            new_dp[j][j] += dp[j][k] * k % mod
            new_dp[j][j] %= mod
            new_dp[j][k] += dp[j][k] * (j - k) % mod
            new_dp[j][k] %= mod
            if j != n:
                new_dp[j + 1][k] += dp[j][k] * (n - j) % mod
                new_dp[j + 1][k] %= mod
    dp = new_dp


print(dp[n][n])

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_f

街を、初めて訪れる順に順番つけすると街の順列を考えずに済むようになる

まだ未訪問を状態0
訪問したが、町1に戻れない街を、状態1
街0にたどり着くことが出来る街を、状態2 とする

出来ることは高々3つ。
未訪問の街に行く→状態0の街が一つ減り、1の街が1つ増える
状態1の街に行く→なにも変化なし
状態2の街に行く→状態1の街が全て2に変わる

あとはこれでdpしてあげて、順列を掛けてあげれば終わり!
→べつにdp推移中に計算すればokだった

dp推移は、dp[未訪問の街の数][状態1の街の数] = 移動の数
でおｋ O(N**3)で解ける。

"""

N,M = map(int,input().split())

dp = [ [0] * N for i in range(N) ]
dp[N-1][0] = 1
mod = 10**9+7

for loop in range(M):

    ndp = [ [0] * N for i in range(N) ]

    for i in range(N):

        for j in range(N):

            
            if i != 0 and j != N-1:
                ndp[i-1][j+1] += dp[i][j] * i
                ndp[i-1][j+1] %= mod

            

            if j > 0:
                ndp[i][j] += dp[i][j] * j
                ndp[i][j] %= mod

            

            ndp[i][0] += dp[i][j] * (N-i-j)
            ndp[i][0] %= mod

    dp = ndp

print (dp[0][0] % mod)

Solution (Python):
n, m = map(int,raw_input().split())
mod = 10 ** 9 + 7
dp=[[[0] * (n + 1) for _ in xrange(n + 1)] for _ in xrange(2)]
dp[0][1][1] = 1
for i in xrange(m):
    for j in xrange(n + 1):
        for k in xrange(n + 1):
            dp[(i+1)%2][j][k] = 0
    for j in xrange(1, n + 1):
        for k in xrange(1, j + 1):
            dp[(i+1)%2][min(j+1,n)][k] += dp[i%2][j][k] * (n - j) % mod
            dp[(i+1)%2][j][k] += dp[i%2][j][k] * (j - k) % mod
            dp[(i+1)%2][j][j] += dp[i%2][j][k] * k % mod
print dp[m%2][n][n] % mod

Solution (Python):
K=10**9+7
N,M=map(int,raw_input().split())
A=[[[0]*(N+2) for j in range(N+2)] for i in range(M+1)]
A[0][1][1]=1
for i in range(M):
	for j in range(N+1):
		for k in range(N+1):
			A[i+1][j+1][k]=(A[i+1][j+1][k]+A[i][j][k]*(N-j))%K
			A[i+1][j][k]=(A[i+1][j][k]+A[i][j][k]*(j-k))%K
			A[i+1][j][j]=(A[i+1][j][j]+A[i][j][k]*k)%K
print A[M][N][N]