时空限制

1S/512M

题目描述

定义一个整数数组 $X_0, X_1, \dots, X_n$。 这个数组的初始项为 $X_0$。后续的每一项都由前一项根据给定的数组 $A = [A_1, \dots, A_n]$ 和 $B = [B_1, \dots, B_n]$ 计算得出。

具体的计算规则如下，对于 $i$ 从 $1$ 到 $n$：

$$X_i = \lfloor \frac{X_{i-1}}{A_i} \rfloor - B_i$$

其中 $\lfloor z \rfloor$ 表示对 $z$ 向下取整。即取不大于 $z$ 的最大整数。例如：

• $\lfloor 3.14 \rfloor = 3$
• $\lfloor 5.0 \rfloor = 5$

现在，我们已知数组的最后一项 $X_n$ 的值等于 $Y$。你的任务是找出所有可能的初始值 $X_0$ 中，最大的一个是多少。

由于答案可能非常大，请输出这个最大的 $X_0$ 对 $998244353$ 取模后的结果。

格式

输入格式

第一行包含一个整数 $n$，表示操作的次数。

第二行包含 $n$ 个整数，表示数组 $A$ 的元素 $A_1, A_2, \dots, A_n$。

第三行包含 $n$ 个整数，表示数组 $B$ 的元素 $B_1, B_2, \dots, B_n$。

第四行包含一个整数 $Y$，表示最终得到的结果。

输出格式

输出一个整数，表示最大的可能初始值 $X_0$ 对 $998244353$ 取模的结果。

样例

样例输入 #1

2
2 3
1 1
5

样例输出 #1

43

样例解释 #1

• 初始值 $X = 43$。
• 第 1 次操作：使用 $A_1=2, B_1=1$。$X$ 变为 $\lfloor \frac{43}{2} \rfloor - 1 = 21 - 1 = 20$。
• 第 2 次操作：使用 $A_2=3, B_2=1$。$X$ 变为 $\lfloor \frac{20}{3} \rfloor - 1 = 6 - 1 = 5$。 结果是 $5$。

可以证明，$43$ 是能得到结果 $5$ 的最大初始值。

数据规模

对于 $20\%$ 的数据，$1 \leq n \leq 5$，$1 \le A_i, B_i \le 10$，$0 \leq Y \leq 10$。

对于 $40\%$ 的数据，$1 \leq n \leq 10$，$1 \le A_i, B_i \le 10$，$0 \leq Y \leq 10$。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$1 \le A_i, B_i \le 10^9$，$0 \le Y \le 10^9$。