<br></br>// Nguyên lý bù trừ

// Độ phức tạp thời gian O(2^n-1)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 2e6 + 10;
ll n, m, ketqua, thamso[MAX];

signed main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) cin >> thamso[i];
    for (int i = 1; i < (1 << m); ++i) { // Duyệt qua tất cả các tổ hợp
        ll dem = 0, tich = 1;
        for (int j = 0; j < m; ++j) {
            if (i & (1 << j)) {
                dem++;
                tich *= thamso[j];
                if (tich > n) break;
            }
        }
        if (dem % 2 == 1) ketqua += n / tich; // Nếu số lượng điều kiện là lẻ, cộng vào kết quả
        else ketqua -= n / tich;
    }
    cout << ketqua << endl;
    return 0;
}

**Các khái niệm cơ bản:**

- |U|: Số phương án tổng thể - Si: Số phương án thỏa mãn điều kiện i - ⋃: Phép toán hợp (biểu thị số phương án thỏa mãn ít nhất một điều kiện) - ⋂: Phép toán giao (biểu thị số phương án thỏa mãn tất cả các điều kiện)

**Công thức nguyên lý bù trừ:**

1. Tính số phương án thỏa mãn ít nhất một điều kiện:

\[|\bigcup_{i=1}^{n} S_i| = \sum_{m=1}^{n} (-1)^{m-1} \sum_{1 \leq i_1 < i_2 < \ldots < i_m \leq n} |\bigcap_{j=1}^{m} S_{i_j}|\]

Công thức này dùng để tính số phương án thỏa mãn ít nhất một điều kiện, trong đó \(m\) biểu thị số lượng điều kiện được thỏa mãn, \(S_{i_j}\) là tập hợp các phương án thỏa mãn điều kiện thứ \(i_j\).

2. Tính số phương án thỏa mãn chính xác tất cả các điều kiện:

\[|\bigcap_{i=1}^{n} S_i| = |U| - |\bigcup_{i=1}^{n} S_i|\]

Công thức này dùng để tính số phương án thỏa mãn chính xác tất cả các điều kiện.

Ý tưởng cốt lõi của nguyên lý bù trừ là chuyển đổi giữa "ít nhất (nhiều nhất)" và "chính xác", thông qua các phép toán giao và hợp để tính số phương án cho các trường hợp khác nhau.

// Chia đặc sản
// https://www.luogu.com.cn/problem/P5505

// Giả sử có i người không nhận được đặc sản thứ j, thì n-i người sẽ chia a[j] phần, theo phương pháp cắm bảng ta có
// Số phương án là C(a[j]+n-i-1,n-i-1), và cần chọn i người, nên có C(n,i) cách, theo nguyên lý nhân
// Sử dụng nguyên lý bù trừ để loại bỏ các trạng thái không hợp lệ
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 5000, MOD = 1e9 + 7;
ll n, m, giaithua[MAX], nghichdao[MAX], k, dac_san[MAX], ketqua;

ll qpow(ll a, ll k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = res * a % MOD;
        a = a * a % MOD, k /= 2;
    }
    return res;
}

ll C(ll a, ll b) {
    return giaithua[a] * nghichdao[b] % MOD * nghichdao[a - b] % MOD;
}

signed main() {
    cin >> n >> m;
    giaithua[0] = nghichdao[0] = 1, k = 1;
    for (int i = 1; i < MAX; ++i) giaithua[i] = giaithua[i - 1] * i % MOD;
    nghichdao[MAX - 1] = qpow(giaithua[MAX - 1], MOD - 2);
    for (int i = MAX - 2; i; --i) nghichdao[i] = (i + 1) * nghichdao[i + 1] % MOD;
    for (int i = 1; i <= m; ++i) cin >> dac_san[i];
    for (int i = 0; i < n; ++i, k = -k) {
        ll tich = 1;
        for (int j = 1; j <= m; ++j) tich = tich * C(dac_san[j] + n - i - 1, n - i - 1) % MOD;
        ketqua = (ketqua + C(n, i) * k % MOD * tich % MOD + MOD) % MOD;
    }
    cout << ketqua;
    return 0;
}