Problem: Lunar New Year is approaching, and Bob received a gift from his friend recently — a recursive sequence! He loves this sequence very much and wants to play with it.

Let f_1, f_2, …, f_i, … be an infinite sequence of positive integers. Bob knows that for i > k, f_i can be obtained by the following recursive equation:

$$$f_i = \left(f_{i - 1} ^ {b_1} ⋅ f_{i - 2} ^ {b_2} ⋅ ⋅⋅⋅ ⋅ f_{i - k} ^ {b_k}\right) mod p,$$$

which in short is

$$$f_i = \left(∏_{j = 1}^{k} f_{i - j}^{b_j}\right) mod p,$$$

where p = 998 244 353 (a widely-used prime), b_1, b_2, …, b_k are known integer constants, and x mod y denotes the remainder of x divided by y.

Bob lost the values of f_1, f_2, …, f_k, which is extremely troublesome – these are the basis of the sequence! Luckily, Bob remembers the first k - 1 elements of the sequence: f_1 = f_2 = … = f_{k - 1} = 1 and the n-th element: f_n = m. Please find any possible value of f_k. If no solution exists, just tell Bob that it is impossible to recover his favorite sequence, regardless of Bob's sadness.

Input

The first line contains a positive integer k (1 ≤ k ≤ 100), denoting the length of the sequence b_1, b_2, …, b_k.

The second line contains k positive integers b_1, b_2, …, b_k (1 ≤ b_i < p).

The third line contains two positive integers n and m (k < n ≤ 10^9, 1 ≤ m < p), which implies f_n = m.

Output

Output a possible value of f_k, where f_k is a positive integer satisfying 1 ≤ f_k < p. If there are multiple answers, print any of them. If no such f_k makes f_n = m, output -1 instead.

It is easy to show that if there are some possible values of f_k, there must be at least one satisfying 1 ≤ f_k < p.

Examples

Input


3
2 3 5
4 16


Output


4


Input


5
4 7 1 5 6
7 14187219


Output


6


Input


8
2 3 5 6 1 7 9 10
23333 1


Output


1


Input


1
2
88888 66666


Output


-1


Input


3
998244352 998244352 998244352
4 2


Output


-1


Input


10
283 463 213 777 346 201 463 283 102 999
2333333 6263423


Output


382480067

Note

In the first sample, we have f_4 = f_3^2 ⋅ f_2^3 ⋅ f_1^5. Therefore, applying f_3 = 4, we have f_4 = 16. Note that there can be multiple answers.

In the third sample, applying f_7 = 1 makes f_{23333} = 1.

In the fourth sample, no such f_1 makes f_{88888} = 66666. Therefore, we output -1 instead.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MOD = 998244353;
const int PMOD = MOD - 1;
const int PROOT = 3;
const int MAXDEG = 100;
int pw(int x, int n) {
  int ret = 1;
  while (true) {
    if (n & 1) ret = (long long)ret * x % MOD;
    if ((n >>= 1) == 0) return ret;
    x = (long long)x * x % MOD;
  }
}
int findprootpow(int x) {
  int bigystep = (int)sqrt(MOD);
  int bigxstep = pw(PROOT, bigystep);
  map<int, int> mp;
  for (int cx = 1, cy = 0; cy < MOD - 1;
       cx = (long long)cx * bigxstep % MOD, cy += bigystep) {
    assert(!mp.count(cx));
    mp[cx] = cy;
  }
  for (int cx = x, cy = 0;; cx = (long long)cx * PROOT % MOD, ++cy)
    if (mp.count(cx)) {
      int ret = mp[cx] - cy;
      if (ret < 0) ret += MOD - 1;
      return ret;
    }
}
int deg;
int b[MAXDEG];
int n, fn;
void printmat(const vector<vector<int>> &A) {
  int h = ((int)(A).size()), w = ((int)(A[0]).size());
  for (int x = (0); x < (h); ++x) {
    for (int y = (0); y < (w); ++y) {
      if (y != 0) printf(" ");
      printf("%d", A[x][y]);
    }
    puts("");
  }
}
vector<vector<int>> mmult(const vector<vector<int>> A,
                          const vector<vector<int>> &B) {
  int dim = ((int)(A).size());
  vector<vector<int>> ret(dim, vector<int>(dim, 0));
  for (int i = (0); i < (dim); ++i)
    for (int j = (0); j < (dim); ++j)
      for (int k = (0); k < (dim); ++k)
        ret[i][j] = (ret[i][j] + (long long)A[i][k] * B[k][j]) % PMOD;
  return ret;
}
vector<vector<int>> mpw(vector<vector<int>> x, int n) {
  int dim = ((int)(x).size());
  vector<vector<int>> ret(dim, vector<int>(dim, 0));
  for (int i = (0); i < (dim); ++i) ret[i][i] = 1;
  while (true) {
    if (n & 1) ret = mmult(ret, x);
    if ((n >>= 1) == 0) return ret;
    x = mmult(x, x);
  }
}
int egcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  int g = egcd(b, a % b, y, x);
  y -= (a / b) * x;
  return g;
}
int solve() {
  vector<vector<int>> A(deg, vector<int>(deg, 0));
  for (int i = (0); i < (deg - 1); ++i) A[i][i + 1] = 1;
  for (int i = (0); i < (deg); ++i) A[deg - 1][deg - i - 1] = b[i];
  vector<vector<int>> B = mpw(A, n - 1);
  int a = B[0][deg - 1], b = findprootpow(fn);
  int x, y, g = egcd(a, PMOD, x, y);
  if (b % g != 0) return -1;
  int z = (long long)(b / g) * x % PMOD;
  if (z < 0) z += PMOD;
  int ret = pw(PROOT, z);
  return ret;
}
void run() {
  scanf("%d", &deg);
  for (int i = (0); i < (deg); ++i) scanf("%d", &b[i]);
  scanf("%d%d", &n, &fn);
  printf("%d\n", solve());
}
int main() {
  run();
  return 0;
}