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;
const long long mod = 998244353;
const long long root = 3;
const long long maxn = 102;
struct node {
  long long cx, c;
};
struct matrix {
  long long n, m;
  node a[maxn][maxn];
} t, tmp;
long long n, m, k;
map<long long, long long> ma;
long long gx, gy;
long long ans;
node operator+(node x1, node x2) {
  node y;
  y.c = (x1.c + x2.c) % (mod - 1);
  y.cx = (x1.cx + x2.cx) % (mod - 1);
  return y;
}
node operator*(node x1, node x2) {
  node y;
  y.c = (x1.c * x2.c) % (mod - 1);
  y.cx = (x1.c * x2.cx + x1.cx * x2.c) % (mod - 1);
  return y;
}
matrix operator*(matrix x1, matrix x2) {
  matrix y;
  long long i, j, l;
  y.n = x1.n;
  y.m = x2.m;
  for (i = 1; i <= y.n; i++)
    for (j = 1; j <= y.m; j++) y.a[i][j].c = y.a[i][j].cx = 0;
  for (i = 1; i <= x1.n; i++)
    for (j = 1; j <= x1.m; j++)
      for (l = 1; l <= x2.m; l++)
        y.a[i][l] = y.a[i][l] + x1.a[i][j] * x2.a[j][l];
  return y;
}
long long pow(long long f, long long x) {
  long long s = 1;
  while (x) {
    if (x % 2) s = (s * f) % mod;
    f = (f * f) % mod;
    x = x / 2;
  }
  return s;
}
long long inv(long long x) { return pow(x, mod - 2); }
matrix pow(matrix f, long long x) {
  matrix s;
  long long i, j;
  s.n = s.m = f.n;
  for (i = 1; i <= s.n; i++)
    for (j = 1; j <= s.m; j++) s.a[i][j].cx = s.a[i][j].c = 0;
  for (i = 1; i <= s.n; i++) s.a[i][i].c = 1;
  while (x) {
    if (x % 2) {
      s = s * f;
    }
    f = f * f;
    x = x / 2;
  }
  return s;
}
long long getlog(long long x) {
  long long i, f = pow(root, 32000ll), s, ret;
  s = 1;
  for (i = 0; i <= 32000; i++) {
    ma[s] = i;
    s = (s * f) % mod;
  }
  s = 1;
  f = inv(root);
  ret = 0;
  for (i = 0; i <= 32000; i++) {
    if (ma.find((x * s) % mod) != ma.end()) {
      ret = ma[(x * s) % mod] * 32000 + i;
      break;
    }
    s = (s * f) % mod;
  }
  if (ret > mod - 1) ret -= mod - 1;
  return ret;
}
long long exgcd(long long a, long long b) {
  if (b == 0) {
    gx = 1;
    gy = 0;
    return a;
  }
  long long ret, xx, yy;
  if (a < b) {
    ret = exgcd(b, a);
    swap(gx, gy);
    return ret;
  }
  ret = exgcd(b, a % b);
  xx = gy;
  yy = gx - (a / b) * gy;
  gx = xx;
  gy = yy;
  return ret;
}
long long getans(long long a, long long r) {
  long long gcd = exgcd(a, mod - 1);
  while (gx < 0) gx += mod - 1;
  if (r % gcd == 0)
    return (gx * r / gcd) % (mod - 1);
  else
    return -1;
}
void work() {
  long long i;
  scanf("%I64d", &k);
  t.n = t.m = k;
  for (i = 1; i <= k; i++) {
    scanf("%I64d", &t.a[k - i + 1][k].c);
  }
  for (i = 1; i < k; i++) {
    t.a[i + 1][i].c = 1;
  }
  scanf("%I64d%I64d", &n, &m);
  tmp.n = 1;
  tmp.m = k;
  for (i = 1; i < k; i++) {
    tmp.a[1][i].c = 0;
  }
  tmp.a[1][k].cx = 1;
  tmp = tmp * pow(t, n - k);
  if (tmp.a[1][k].cx == 0) {
    if (tmp.a[1][k].c == getlog(m)) {
      printf("1\n");
    } else
      printf("-1\n");
    return;
  }
  ans =
      getans(tmp.a[1][k].cx, (getlog(m) - tmp.a[1][k].c + mod - 1) % (mod - 1));
  if (ans == -1)
    printf("-1\n");
  else
    printf("%I64d\n", pow(root, ans));
}
int main() {
  work();
  return 0;
}