CF756E Byteland coins

在 Byteland，有 $n$ 种不同面额的硬币。方便的是，第 $k$ 种硬币的面额可以整除第 $k+1$ 种硬币的面额，第 $1$ 种硬币的面额为 $1$ tugrick。第 $k+1$ 种和第 $k$ 种硬币面额的比值为 $a_{k}$。已知，对于每一个面额 $x$，最多只会有 $20$ 种硬币的面额等于 $x$。 Byteasar 拥有 $b_{k}$ 枚第 $k$ 种硬币，他需要用这些硬币恰好支付 $m$ tugrick。已知他拥有的所有硬币总数不会超过 $3·10^{5}$。Byteasar 想知道，用这些硬币恰好支付 $m$ tugrick 有多少种方案。如果在某一种方案下，存在某个 $k$，第 $k$ 种硬币的数量与另一种方案不同，则这两种方案视为不同的方案。与所有 Byteland 公民一样，Byteasar 想知道答案对 $10^{9}+7$ 取模的值。

第一行包含一个整数 $n$（$1\leq n\leq 3·10^{5}$），表示硬币的种类数。 第二行包含 $n-1$ 个整数 $a_{1}$，$a_{2}$，$\ldots$，$a_{n-1}$（$1\leq a_{k}\leq 10^{9}$），表示相邻两种硬币面额之间的比值。保证每一种面额 $x$ 最多只会出现 $20$ 种硬币面额等于 $x$。 第三行包含 $n$ 个非负整数 $b_{1}$，$b_{2}$，$\ldots$，$b_{n}$，表示 Byteasar 拥有的每种硬币的数量。保证这些数量之和不超过 $3·10^{5}$。 第四行包含一个整数 $m$（$0\leq m

输出一个整数，表示恰好支付 $m$ tugrick 的方案数，对 $10^{9}+7$ 取模。

在第一个样例中，Byteasar 手上有 $4$ 枚面额为 $1$ 的硬币，他需要支付 $2$ tugrick，总共有 $1$ 种方案。 在第二个样例中，Byteasar 分别有两种面额为 $1$ 的硬币，每种各 $4$ 枚，他需要支付 $2$ tugrick。共有 $3$ 种方案：第一种用第一种硬币 $2$ 枚，第二种用第二种硬币 $2$ 枚，第三种用两种各用 $1$ 枚。 在第三个样例中，硬币面额分别为 $1$、$3$、$9$。 由 ChatGPT 5 翻译