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



Sample input:
3 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
# dp[i][j] := i 回の移動で頂点 1 から自由に j 個行き来できて王様がその中にいる場合の数
# O(N^2 M^2) の解を書こうと思ったけど最後に戻ってこないパターンが抜けてる
# 面倒になって諦め

exit()

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  # 上昇階乗冪 n * (n+1) * ... * (n+r-1)
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  # 第 1 種スターリング数  lru_cache を使うと O(nk)  # n 要素を k 個の巡回列に分割する場合の数
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  # 第 2 種スターリング数 O(k + log(n))  # n 要素を区別のない k グループに分割する場合の数
        if n == k: return 1  # n==k==0 のときのため
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  # n 要素を区別のある k グループに分割する場合の数  O(k + log(n))
        if n < k: return 0
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  # ベルヌーイ数  lru_cache を使うと O(n**2 * log(mod))
        if n == 0: return 1
        if n % 2 and n >= 3: return 0  # 高速化
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  # べき乗和 0^k + 1^k + ... + (n-1)^k
        # bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  # n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1)
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  # n 要素を k グループ以下に分割する場合の数  O(k**2 + k*log(mod))
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod


mod = 10**9+7
comb = Combination(300, mod)
balls_and_boxes_3 = [[0] * 301 for _ in range(301)]
for n in range(301):
    for k in range(301):
        balls_and_boxes_3[n][k] = comb.balls_and_boxes_3(n, k)

N, M = map(int, input().split())
dp = [[0] * (N+1) for _ in range(M+1)]
dp[0][1] = 1
for i in range(1, M+1):
    for j in range(1, N+1):
        n, k = 1, 0
        dp[i][j] += dp[i-1][j] * j % mod
        for n in range(1, i+1):
            for k in range(1, min(j-1, n)+1):  # k=0 の場合も
                dp[i][j] += dp[i-n][j-k] * comb.C(N-(j-k), k) % mod * balls_and_boxes_3[n-1][k] % mod * (j-k) % mod

for d in dp:
    print(d)

print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
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(1, n + 1):
        for k in xrange(1, j + 1):
            dp[(i+1)&1][min(j+1,n)][k] += dp[i&1][j][k] * (n - j)  % mod
            dp[(i+1)&1][j][k] += dp[i&1][j][k] * (j - k) % mod
            dp[(i+1)&1][j][j] += dp[i&1][j][k] * k % mod
print dp[m&1][n][n] % mod

Submission status: Wrong Answer

Solution code:
import numpy as np
N = 150
M = 300
# one way path from 1, no path from 1
status_mat = np.zeros((N, N), dtype='int')
status_mat[0, N-1] = 1

bothM = np.zeros((N, N), dtype='int')
for i in range(N):
    for j in range(N):
        bothM[i, j] = N-i-j

diagM = np.diag(range(N))



def update_status_mat(status_mat):
    new_status_mat = diagM.dot(status_mat)
    new_status_mat[0, :] += (bothM*status_mat).sum(axis=0)
    new_status_mat[1:, :(N-1)] += status_mat.dot(diagM)[:(N-1), 1:]
    return new_status_mat % 1000000007

for m in range(M):
    status_mat = update_status_mat(status_mat)

print status_mat[0,0]

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, raw_input().split())
# one way path from 1, no path from 1
status_mat = np.zeros((N, N), dtype='int')
status_mat[0, N-1] = 1

bothM = np.zeros((N, N), dtype='int')
for i in range(N):
    for j in range(N):
        bothM[i, j] = N-i-j

diagM = np.diag(range(N))



def update_status_mat(status_mat):
    status_mat[0, 0] = 0
    new_status_mat = diagM.dot(status_mat)
    new_status_mat[0, :] += (bothM*status_mat).sum(axis=0)
    new_status_mat[1:, :(N-1)] += status_mat.dot(diagM)[:(N-1), 1:]
    return new_status_mat % 1000000007

for m in range(M):
    status_mat = update_status_mat(status_mat)

print status_mat[0,0]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, raw_input().split())
# one way path from 1, no path from 1
status_mat = np.zeros((N, N), dtype='int')
status_mat[0, N-1] = 1

bothM = np.zeros((N, N), dtype='int')
for i in range(N):
    for j in range(N):
        bothM[i, j] = N-i-j

diagM = np.diag(range(N))



def update_status_mat(status_mat):
    new_status_mat = diagM.dot(status_mat)
    new_status_mat[0, :] += (bothM*status_mat).sum(axis=0)
    new_status_mat[1:, :(N-1)] += status_mat.dot(diagM)[:(N-1), 1:]
    return new_status_mat % 1000000007

for m in range(M):
    status_mat = update_status_mat(status_mat)

print status_mat[0,0]

Submission status: Memory Limit Exceeded

Solution code:
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)] for _ in range(m + 1)]
dp[0][1][1] = 1
for i in range(m):
    for j in range(1, n + 1):
        for k in range(1, j + 1):
            dp[i + 1][j][j] += dp[i][j][k] * k % mod
            dp[i + 1][j][j] %= mod
            dp[i + 1][j][k] += dp[i][j][k] * (j - k) % mod
            dp[i + 1][j][k] %= mod
            if j != n:
                dp[i + 1][j + 1][k] += dp[i][j][k] * (n - j) % mod
                dp[i + 1][j + 1][k] %= mod


print(dp[m][n][n])

Submission status: Memory Limit Exceeded

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

Submission status: Memory Limit Exceeded

Solution code:
K=10**9+7
N,M=map(int,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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:

"""
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

            #状態1の街に行く(少なくとも1つある場合)

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

            #状態2の街に行く

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

    dp = ndp

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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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]

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, raw_input().split())
# one way path from 1, no path from 1
status_mat = np.zeros((N, N), dtype='int')
status_mat[0, N-1] = 1
 
bothM = np.zeros((N, N), dtype='int')
for i in range(N):
    for j in range(N):
        bothM[i, j] = N-i-j
 
diagM = np.diag(range(N))
 
 
 
def update_status_mat(status_mat):
    new_status_mat = diagM.dot(status_mat)
    new_status_mat[0, :] += (bothM*status_mat).sum(axis=0)
    new_status_mat[1:, :(N-1)] += status_mat.dot(diagM)[:(N-1), 1:]
    return new_status_mat % 1000000007
 
for m in range(M):
    status_mat = update_status_mat(status_mat)
 
print status_mat[0,0]