Description:

Niuniu likes mathematics. He also likes drawing pictures. One day, he was trying to draw a regular polygon with n vertices. He connected every pair of the vertices by a straight line as well. He counted the number of regions inside the polygon after he completed his picture. He was wondering how to calculate the number of regions without the picture. Can you calculate the number of regions modulo 1000000007? It is guaranteed that n is odd.

Input:

The only line contains one odd number n(3 ≤ n ≤ 1000000000), which is the number of vertices.

Output:

Print a single line with one number, which is the answer modulo 1000000007.

Sample Input:

3

Sample Output:

1

Sample Input:

5

Sample Output:

11

Hint:

The following picture shows the picture which is drawn by Niuniu when n=5. Note that no three diagonals share a point when n is odd.

题目链接

先观察顶点数和结果的关系:

vertices ans
3 1
4 4
5 11
6 24
7 50

之后丢入OEIS中(手动滑稽…并不会正解)

即可得到此数列的详细介绍，根据公式求出结果

a ( n ) = 24 − 42 n + 23 n 2 − 6 n 3 + n 4 24 a(n) = \frac{24 - 42n + 23n^2 - 6n^3 + n^4}{24} a(n)=2424−42n+23n2−6n3+n4​

因为此题有取模运算，所以需要求出24对1e9+7的逆元进行计算。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x)
#define XDebug(x) cout<<#x<<"="<<x<<endl;
#define ArrayDebug(x,i) cout<<#x<<"["<<i<<"]="<<x[i]<<endl;
#define print(x) out(x);putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 5e4 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) {
        return 0;
    }
    while (c != '-' && (c < '0' || c > '9')) {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}
template <class T>
inline void out(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        out(x / 10);
    }
    putchar(x % 10 + '0');
}

ll QuickMul(ll a, ll b) {
	ll res = 0;
	while (b) {
		if (b & 1) {
			res = (res + a) % mod;
		}
		a = (a + a) % mod;
		b >>= 1;
	}
	return res;
}

ll QuickPow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) {
			res = QuickMul(res, a) % mod;
		}
		a = QuickMul(a, a) % mod;
		b >>= 1;
	}
	return res;
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	ll n;
	while (read(n)) {
		ll ans = ((24 - 42 * n + 23 * QuickPow(n, 2) - 6 * QuickPow(n, 3) + QuickPow(n, 4)) * 41666667) % mod;
		ans = (ans + mod) % mod;
		print(ans);
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}