题目描述

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