题目描述

我们把一个数称为有趣的，当且仅当：

它的数字只包含 0,1,2,3，且这四个数字都出现过至少一次。
所有的 0 都出现在所有的 1 之前，而所有的 2 都出现在所有的 3 之前。
最高位数字不为 0。
因此，符合我们定义的最小的有趣的数是 2013。

除此以外，4 位的有趣的数还有两个：2031 和 2301。

请计算恰好有 n 位的有趣的数的个数。

由于答案可能非常大，只需要输出答案除以 109+7 的余数。

输入格式
输入只有一行，包括恰好一个正整数 n。

输出格式
输出只有一行，包括恰好 n 位的整数中有趣的数的个数除以 109+7 的余数。

数据范围
4≤n≤1000

样例

输入样例：
4
输出样例：
3

算法1

(组合计数)

C++ 代码

#include<iostream>
using namespace std;
const int N = 1005;
const int MOD = 1e9+7;
typedef long long ll;
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]+c[i-1][j-1])%MOD;
        }
    }
    int ans=0;
    for(int k=2;k<=n;k++){
        ans=(ans+ll(c[n-1][k])*(k-1) % MOD * (n-k-1))%MOD;
    }
    cout<<ans;
    return 0;
}