CF865G Flowers and Chocolate

Piegirl 的生日快到了，Pieguy 决定为她购买一束花和一个装巧克力的篮子。 花店有 $F$ 种不同类型的花可供选择。第 $i$ 种花恰好有 $p_{i}$ 片花瓣。Pieguy 决定买一束由恰好 $N$ 朵花组成的花束。他可以多次购买同一种花。这 $N$ 朵花的排列顺序是有区别的，因此可以将一束花看作花的类型的一个有序序列。 巧克力店以盒子售卖巧克力。一共有 $B$ 种不同类型的盒子。第 $i$ 种盒子中装有 $c_{i}$ 块巧克力。Pieguy 可以购买任意数量的盒子，同一种盒子可以购买多次。然后他会把这些盒子放入一个篮子中。盒子在篮子中的排列顺序是有区别的，因此可以将篮子看作盒子类型的一个有序序列。 Pieguy 知道 Piegirl 喜欢在吃每一块巧克力之前先摘下一片花瓣。他希望确保她在摘下最后一朵花的最后一片花瓣之后，恰好吃完最后一盒的最后一块巧克力。也就是说，花束中所有花的花瓣总数要等于篮子里所有盒子中的巧克力总数。 请问 Pieguy 可以购买多少种不同的花束和篮子的组合？答案可能很大，请将结果对 $1000000007=10^9+7$ 取模后输出。

输入的第一行包含三个整数 $F$、$B$ 和 $N$（$1 \leq F \leq 10$，$1 \leq B \leq 100$，$1 \leq N \leq 10^{18}$），表示花的种类数、盒子的种类数和花束中花的数量。 第二行包含 $F$ 个整数 $p_1, p_2, \cdots, p_F$（$1 \leq p_i \leq 10^9$），分别表示每种花的花瓣数。 第三行包含 $B$ 个整数 $c_1, c_2, \cdots, c_B$（$1 \leq c_i \leq 250$），分别表示每种盒子里的巧克力数量。

请输出 Pieguy 能买到的不同花束和篮子组合的方案数，对 $1000000007=10^9+7$ 取模。

在第一个样例中，只有 $1$ 种方法能用 $9$ 片花瓣组成一束花 $(3+3+3)$，只有 $1$ 种方法能用 $9$ 块巧克力装满篮子 $(3+3+3)$，共 $1$ 种组合；有 $3$ 种方法能用 $13$ 片花瓣组成花束 $(3+5+5,5+3+5,5+5+3)$，有 $5$ 种方法能用 $13$ 块巧克力装满篮子 $(3+10,10+3,3+3+7,3+7+3,7+3+3)$，共 $15$ 种组合。最后有 $1$ 种方法能用 $15$ 片花瓣组成花束 $(5+5+5)$，有 $1$ 种方法能用 $15$ 块巧克力装满篮子 $(3+3+3+3+3)$，共 $1$ 种组合。 注意，不同种类的花即使有相同的花瓣数，也被视为不同。同样，不同种类的盒子即使含有相同数量的巧克力，也被视为不同。 由 ChatGPT 5 翻译