农历新年即将来临,鲍勃最近收到了朋友的一份礼物——递归序列!他非常喜欢这个序列并且想玩它。
令 $$$f_1, f_2, \ldots, f_i, \ldots$$$ 为正整数的无限序列。 Bob 知道,对于 $$$i > k$$$,$$$f_i$$$ 可以通过以下递归方程获得:
$$$$$$f_i = \left(f_{i - 1} ^ {b_1} \cdot f_{i - 2} ^ {b_2} \cdot \cdots \cdot f_{i - k} ^ {b_k}\right) \bmod p,$$$$$$
简而言之就是
$$$$$$f_i = \left(\prod_{j = 1}^{k} f_{i - j}^{b_j}\right) \bmod p,$$$$$$
其中$$$p = 998\,244\,353$$$(广泛使用的素数),$$$b_1, b_2, \ldots, b_k$$$ 是已知的整数常量,$$$x \bmod y$$$ 表示$$$x$$$ 除以$$$y$$$ 的余数。
Bob丢失了$$$f_1、f_2、\ldots、f_k$$$的值,这非常麻烦——这些是序列的基础!幸运的是,Bob 记住了序列的前 $$$k - 1$$$ 元素:$$$f_1 = f_2 = \ldots = f_{k - 1} = 1$$$ 和第 $$$n$$$ 个元素:$$$f_n = m$$$。请找出 $$$f_k$$$ 的任何可能值。如果不存在解决方案,只需告诉鲍勃无论鲍勃多么悲伤,都不可能恢复他最喜欢的序列。
输入
第一行包含一个正整数 $$$k$$$ ($$$1 \leq k \leq 100$$$),表示序列 $$$b_1, b_2, \ldots, b_k$$$ 的长度。
第二行包含 $$$k$$$ 正整数 $$$b_1, b_2, \ldots, b_k$$$ ($$$1 \leq b_i < p$$$)。
第三行包含两个正整数 $$$n$$$ 和 $$$m$$$ ($$$k < n \leq 10^9$$$, $$$1 \leq m < p$$$),这意味着 $$$f_n = m$$$。
输出
输出 $$$f_k$$$ 的可能值,其中 $$$f_k$$$ 是满足 $$$1 \leq f_k < p$$$ 的正整数。如果有多个答案,请打印其中任何一个。如果没有这样的$$$f_k$$$ 使得$$$f_n = m$$$,则输出$$$-1$$$。
很容易证明,如果$$$f_k$$$有一些可能的值,则必须至少有一个满足$$$1 \leq f_k < p$$$。
示例
输入 #1
3 2 3 5 4 16
输出 #1
4
输入 #2
5 4 7 1 5 6 7 14187219
输出 #2
6
输入 #3
8 2 3 5 6 1 7 9 10 23333 1
输出 #3
1
输入#4
1 2 88888 66666
输出#4
-1
输入 #5
3 998244352 998244352 998244352 4 2
输出 #5
-1
输入 #6
10 283 463 213 777 346 201 463 283 102 999 2333333 6263423
输出 #6
382480067
注意
在第一个示例中,我们有 $$$f_4 = f_3^2 \cdot f_2^3 \cdot f_1^5$$$。因此,应用$$$f_3 = 4$$$,我们有$$$f_4 = 16$$$。请注意,可能有多个答案。
在第三个示例中,应用 $$$f_7 = 1$$$ 使得 $$$f_{23333} = 1$$$。
在第四个样本中,没有这样的$$$f_1$$$ 使得$$$f_{88888} = 66666$$$。因此,我们输出$$$-1$$$。