1 #include<bits/stdc++.h> 2 using namespace std; 3 template <class _T> inline void read(_T &_x) { 4     int _t; bool flag = false; 5     while ((_t = getchar()) != ‘-‘ && (_t < ‘0‘ || _t > ‘9‘)) ; 6     if (_t == ‘-‘) _t = getchar(), flag = true; _x = _t - ‘0‘; 7     while ((_t = getchar()) >= ‘0‘ && _t <= ‘9‘) _x = _x * 10 + _t - ‘0‘; 8     if (flag) _x = -_x; 9 }10 typedef long long LL;11 const int maxw = 1010;12 const int maxd = 110;13 const int mod = 1e9 + 7;14 inline int mul(int a, int b) {return (int)((LL)a * b % mod); }15 inline int add(int a, int b) {16     a += b;17     if (a < 0) a += mod; if (a >= mod) a -= mod;18     return a;19 }20 int qpow(LL a, LL b) {21     if (b < 0) return qpow(qpow(a, mod - 2), -b);22     LL ret = 1;23     while (b) {24         if (b & 1) (ret *= a) %= mod;25         (a *= a) %= mod, b >>= 1;26     }27     return (int)ret;28 }29 int H(int i, int p, int a, int d) {30     return mul(qpow(p, (LL)a * i), add(1, -qpow(p, d - i)));31 }32 int A[maxd][maxd], X[maxd];33 inline void init(int d) {34     static int sum[maxd];35     sum[0] = 0;36     for (int i = 1; i <= d + 2; ++i) {37         sum[i] = add(sum[i - 1], qpow(i, d));38         A[i - 1][d + 2] = sum[i], A[i - 1][0] = 1;39         for (int j = 1; j <= d + 1; ++j) A[i - 1][j] = mul(A[i - 1][j - 1], i);40     }41     for (int i = 0, tmp; i <= d + 1; ++i) {42         int to = i;43         while (to <= d + 1 && !A[to][i]) break;44         if (i != to) swap(A[i], A[to]);45         for (int j = 0; j <= d + 1; ++j) if (j != i && A[j][i]) {46            tmp = mul(A[j][i], qpow(A[i][i], mod - 2));47            for (int k = 0; k <= d + 2; ++k) A[j][k] = add(A[j][k], -mul(tmp, A[i][k]));48         }49     }50     for (int i = 0; i <= d + 1; ++i) {51         X[i] = mul(A[i][d + 2], qpow(A[i][i], mod - 2));52     }53 }54 int d, w, p[maxw], a[maxw];55 int main() {56     //freopen(".in", "r", stdin);57     //freopen(".out", "w", stdout);58     read(d), read(w);59     for (int i = 1; i <= w; ++i) read(p[i]), read(a[i]);60     init(d);61     int ans = 0;62     for (int i = 1; i <= d + 1; ++i) {63         int ret = X[i];64         for (int j = 1; j <= w; ++j)65             ret = mul(ret, H(i, p[j], a[j], d));66         ans = add(ans, ret);67     }68     cout << ans << endl;69     return 0;70 }