← 返回题目列表

Codeforces · 1106/F

F. 农历新年和递归序列

中文机器翻译题面 查看原题

农历新年即将来临,鲍勃最近收到了朋友的一份礼物——递归序列!他非常喜欢这个序列并且想玩它。

令 $$$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$$$。