算法：组合计数

时间复杂度：$O(N^2)$

问题可划分为两类，分别为填数字 $0、1$ 和 填数字 $2、3$ 两类，设填数字 $0、1$ 共占 $k$ 位，则填数字 $2、3$ 占 $n - k$ 位，显然 $k$ 的取值范围为 $2 \le k \le n-2$。

$C_{n-1}^{k}$ 为填数字 $0、1$ 的所有占位情况，其中 $0、1$ 的所有取值的情况有 $k-1$ 种，且 $2、3$ 的所有取值的情况有 $n-k-1$ 种，所以共有 $C_{n-1}^{k} \times (k-1) \times (n-k-1)$ 情况。

则最终答案为：$\sum_{k=2}^{n-2}C_{n-1}^{k} \times (k-1) \times (n-k-1)$

C++ 代码

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1010, MOD = 1e9 + 7;
int n;
int C[N][N];

int main()
{
    cin >> n;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (!j) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }
    int res = 0;
    for (int i = 2; i <= n - 2; ++i) {
        res = (res + (LL) C[n - 1][i] * (i - 1) % MOD * (n - i - 1)) % MOD;
    }
    cout << res << endl;
    return 0;
}