acwing1487. 取硬币（背包）

现在有 n1+n2 种面值的硬币，其中前 n1 种为普通币，可以取任意枚，后 n2 种为纪念币，每种最多只能取 1 枚，每种硬币有一个面值，问能用多少种方法拼出 m 的面值？

输入格式
第一行包含三个整数 n1,n2,m，分别表示普通币种类数，纪念币种类数和目标面值；

第二行 n1 个整数，第 i 种普通币的面值 a[i]。保证 a[i] 为严格升序；

第三行 n2 个整数，第 i 种纪念币的面试 b[i]。保证 b[i] 为严格升序。

输出格式
共一行，包含一个整数 x，表示方法总数对 109+7 取模后的结果。

注意，不要忘记取模。

数据范围
对于 30% 的数据，保证 1≤n1+n2≤10,1≤m≤100,1≤a[i]≤100,1≤b[i]≤100。
对于 100% 的数据，保证 1≤n1+n2≤100,1≤m≤100000,1≤a[i]≤100000,1≤b[i]≤100000。

输入样例：
3 1 5
1 2 3
1
输出样例：
9
样例解释
(x) 代表面值为x的普通币，[x]代表面值为x的纪念币，样例所有方法数如下：

(1)(1)(1)(1)(1)
(1)(1)(1)(2)
(1)(1)(3)
(1)(2)(2)
(2)(3)
(1)(1)(1)(1)[1]
(1)(1)1
(1)1
1(2)

#include <iostream>
using namespace std;
const int N = 100010;
int n1, n2, m, mod = 1e9 + 7;
int f[N];
int main() {
    cin >> n1 >> n2 >> m;
    f[0] = 1;
    for (int i = 1; i <= n1; ++i) {
        int p;
        cin >> p;
        for (int j = p; j <= m; ++j) f[j] = (f[j] + f[j - p]) % mod;
    }
    for (int i = 1; i <= n2; ++i) {
        int p;
        cin >> p;
        for (int j = m; j >= p; --j) f[j] = (f[j] + f[j - p]) % mod;
    }
    cout << f[m] << endl;
    return 0;
}