#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int MOD = 1000000007; const int MOD_INV4 = 250000002; void combination(int n, vector >& comb) { comb.assign(n+1, vector(n+1, 0)); for(int i=0; i<=n; ++i){ comb[i][0] = 1; for(int j=1; j<=i; ++j) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD; } } int main() { int n; cin >> n; if(n < 3){ cout << 0 << endl; return 0; } vector > comb; combination(n, comb); vector dp(n+1, 0); dp[0] = dp[1] = dp[2] = 2; for(int i=3; i<=n; ++i){ for(int j=0; j