1. using ll = long long;
    2. constexpr int P = 1000000007;
    3. // assume -P <= x < 2P
    4. int norm(int x) { if (x < 0) x += P; else if (x >= P) x -= P; return x; }
    5. // 快速幂
    6. template <class T> T power(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }
    7. struct Int {
    8.     int x;
    9.     Int(int x = 0) : x(norm(x)) {}
    10.     int val() const { return x; }
    11.     Int operator-() const { return Int(norm(P - x)); }
    12.     Int inv() const { assert(x != 0); return power(*this, P - 2); }
    13.     Int &operator*=(const Int &rhs) { x = ll(x) * rhs.x % P; return *this; }
    14.     Int &operator+=(const Int &rhs) { x = norm(x + rhs.x); return *this; }
    15.     Int &operator-=(const Int &rhs) { x = norm(x - rhs.x); return *this; }
    16.     Int &operator/=(const Int &rhs) { return *this *= rhs.inv(); }
    17.     friend Int operator*(const Int &lhs, const Int &rhs) { Int res = lhs; res *= rhs; return res; }
    18.     friend Int operator+(const Int &lhs, const Int &rhs) { Int res = lhs; res += rhs; return res; }
    19.     friend Int operator-(const Int &lhs, const Int &rhs) { Int res = lhs; res -= rhs; return res; }
    20.     friend Int operator/(const Int &lhs, const Int &rhs) { Int res = lhs; res /= rhs; return res; }
    21.     friend ostream& operator << (ostream& out, const Int &x) { out << x.val(); return out; }
    22. };
    24. // 阶乘和逆元
    25. Int fac[N], inv[N];
    26. inline Int C(int A, int B){ return fac[A] * inv[B] * inv[A - B]; }
    27. /*** main ***/
    28. // 搞清楚 n 的范围
    29. n = N - 1;
    30. fac[0] = 1;
    31. for(int i = 1; i <= n; i++) fac[i] = fac[i-1] * i;
    32. inv[n] = fac[n].inv();
    33. for(int i = n - 1; i >= 0; i--) inv[i] = inv[i+1] * (i + 1);
    34. /*** endmain ***/