题目描述
圣巢里的货币单位称为吉欧。有 $n$ 种面值的货币，满足第 $k + 1$ 种面值的货币是第 $k$ 种面值货币的 $a_k$ 倍。第 $1$ 种货币的面值是 $1$ 吉欧。同一种面值的货币不会超过 $20$ 种。
里姆有 $b_k$ 种 $k$ 类型的吉欧，它需要买下你的一个价值 $m$ 吉欧的文物。由于你不纯粹，你想帮里姆计算出它有几种付款的方式，对 $998244353$ 取模。
付款方式不同当且仅当存在一种货币，它在两种付款方式里的出现次数不同。
输入格式
第一行一个数 $n$。
接下来一行 $n - 1$个整数，$a_{1\cdots n - 1}$。
第三行 $n$ 个整数表示 $b_{1\cdots n}$。
第四行一个整数 $m$。
输出格式
一行一个数，表示答案。
数据范围
$a_i > 0,b_i,m \geq 0$
| 子任务编号 | $n \leq$ | $a_i$ | $\sum b_i \leq$ | $m \leq$ | 分值 |
|---|---|---|---|---|---|
| $1$ | $10$ | $=2$ | $50$ | $10^3$ | 15 |
| $2$ | $10^3$ | $\leq 10^3$ | $50$ | $10^{18}$ | 12 |
| $3$ | $10^4$ | $1 < a_i \leq 3$ | $10^3$ | $10^{18}$ | 14 |
| $4$ | $10^5$ | $=2$ | $2 \times 10^5$ | $10^{10000}$ | 12 |
| $5$ | $2\times 10^5$ | $\leq 2\times 10^5$ | $2\times 10^5$ | $10^{10000}$ | 10 |
| $6$ | $2\times 10^5$ | $1 < a_i < 10^6$ | $2\times 10^5$ | $10^{10000}$ | 15 |
| $7$ | $5\times 10^5$ | $\leq 10^6$ | $5\times 10^5$ | $10^{10000}$ | 22 |
特别地，子任务 6 所有数据均在合法范围内随机。