Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:1024 MB
Statistics

题目描述

圣巢里的货币单位称为吉欧。有 $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 所有数据均在合法范围内随机。