Shared code

//{{{
#pragma GCC diagnostic ignored "-Wunknown-pragmas"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define sz(x) (int)((x).size())
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
// clang-format off
void _print() { cerr << "]\033[0m\n"; }
template <typename T> void __print(T x) { cerr << x; }
template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifdef LOCAL
#define debug(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m["; _print(x)
#define debug_arr(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m" << (x) << "\033[0m\n"
#else
#define debug(x...)
#define debug_arr(x...)
#endif
// clang-format on
//}}}
 
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
LL dp[N][N][2];
void add(LL& a, LL b) { a = (a + b) % mod; }
int n;
 
int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif
 
    while (cin >> n)
    {
        clr(dp, 0);
        dp[1][0][0] = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j <= i - 1; j++)
            {
                // 0
                if (dp[i][j][0])
                {
                    //  not near *i*
                    // dp[i + 1][j][0] += dp[i][j][0] * (i - 1 - j);
                    add(dp[i + 1][j][0], dp[i][j][0] * (i - 1 - j));
                    if (j > 0)
                    {
                        // dp[i + 1][j - 1][0] += dp[i][j][0] * j;
                        add(dp[i + 1][j - 1][0], dp[i][j][0] * j);
                    }
                    //  near *i*
                    add(dp[i + 1][j + 1][1], dp[i][j][0] * 2);
                    // dp[i + 1][j + 1][1] += dp[i][j][0] * 2;
                }
 
                if (dp[i][j][1])
                {
                    assert(j > 0);
 
                    // 1
                    //  not near *i*
                    // dp[i + 1][j][0] += dp[i][j][1] * (i - j);
 
                    add(dp[i + 1][j][0], dp[i][j][1] * (i - j));
 
                    if (j - 1 > 0)
                    {
                        // dp[i + 1][j - 1][0] += dp[i][j][1] * (j - 1);
                        add(dp[i + 1][j - 1][0], dp[i][j][1] * (j - 1));
                    }
 
                    //  near *i*
                    // dp[i + 1][j + 1][1] += dp[i][j][1];  //  i, i+1, i-1
                    // dp[i + 1][j][1] += dp[i][j][1];      // i + 1, i,  i-1
                    add(dp[i + 1][j + 1][1], dp[i][j][1]);
                    add(dp[i + 1][j][1], dp[i][j][1]);
                }
            }
        }
        cout << dp[n][0][0] << endl;
    }
 
    return 0;
}