2223: 取硬币

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

数据范围：

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

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

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

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

共一行，包含一个整数 x，表示方法总数对 10⁹+7 取模后的结果。

注意，不要忘记取模。

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](2)

(1)[1](3)

[1](2)(2)