Submission #1513492

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

const int mod = 1e9 + 7;

int dp[301][301][301];
int N, M;

int64 rec(int idx, int connect, int add)
{
  if(idx == M) return (connect == N);
  if(~dp[idx][connect][add]) return (dp[idx][connect][add]);
  int64 ret = 0;
  if(connect + add + 1 <= N) ret += rec(idx + 1, connect, add + 1) * (N - connect - add) % mod;
  if(add > 0) ret += rec(idx + 1, connect, add) * add % mod;
  ret += rec(idx + 1, connect + add, 0) * connect % mod;
  ret %= mod;
  return (dp[idx][connect][add] = ret);
}

int main()
{
  cin >> N >> M;
  memset(dp, -1, sizeof(dp));
  cout << rec(0, 1, 0) << endl;
}

Submission Info

Judge Result