#include #include #include #define N 5000000 #define LL long long const LL mod = (LL)1e9 + 7; LL a[N],b[N]; #define Int LL Int gcd(Int a, Int b) { return b != 0 ? gcd(b, a % b) : a; } Int lcm(Int a, Int b) { return a * b / gcd(a, b); } // a x + b y = gcd(a, b) Int extgcd(Int a, Int b, Int &x, Int &y) { Int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; } Int invMod(Int a, Int m) { Int x, y; if (extgcd(a, m, x, y) == 1) return (x + m) % m; else return 0; // unsolvable } struct modset{ LL n; LL ndash; LL s; LL mask; int shift; modset(LL n){ n = mod; LL r = 1; shift = 0; while (r < n)r <<= 1, shift++; mask = r - 1; s = ((r%n)*(r%n)) % n; ndash = r - invMod(n, r); } }; using namespace std; int main(){ int ss; cin >> ss; for (int i = 0; i < N; i++){ a[i] = i+1; b[i] = mod-i+1; } for (int i = 0; i < N; i++){ a[i] = (a[i] * b[i]) % mod; } // // // modset x(mod); // //// st = clock(); // // for (int i = 0; i < N; i++){ // LL T, k; // T = a[i] * x.s; // k = (T + (((T&x.mask)*x.ndash)&x.mask)*x.n) >> x.shift; // k = (k < x.n) ? k : k - x.n; // k *= b[i]; // k = (k + (((k&x.mask)*x.ndash)&x.mask)*x.n) >> x.shift; // a[i] = (k < x.n) ? k : k - x.n; // // } // //cout << "mong:" << clock() - st << endl; // cout << 0 << endl; }