CF1106F Lunar New Year and a Recursive Sequence

农历新年即将到来，Bob 最近收到了一份来自朋友的礼物——一个递归数列！他非常喜欢这个数列，想要玩一玩。 设 $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$ 的值。如果不存在这样的 $f_k$，无论 Bob 多么伤心，也请你告诉他无法恢复他心爱的数列。

第一行包含一个正整数 $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$。

输出一个满足 $1 \leq f_k < p$ 的 $f_k$ 的可能取值。如果有多个答案，输出其中任意一个。如果不存在这样的 $f_k$ 使得 $f_n = m$，则输出 $-1$。 可以证明，如果存在可行的 $f_k$，那么一定存在一个满足 $1 \leq f_k < p$ 的解。

在第一个样例中，有 $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$。 由 ChatGPT 4.1 翻译