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;
namespace IO {
template <class T>
inline void readin(T& x) {
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  if (f) x = -x;
}
template <class T>
inline T readin(T x) {
  x = 0;
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  return f ? -x : x;
}
template <class T>
void fwrit(const T x) {
  if (x < 0) return (void)(putchar('-'), fwrit(-x));
  if (x > 9) fwrit(x / 10);
  putchar(x % 10 ^ 48);
}
template <class T>
inline T Max(const T x, const T y) {
  return x < y ? y : x;
}
template <class T>
inline T Min(const T x, const T y) {
  return x < y ? x : y;
}
template <class T>
inline T fab(const T x) {
  return x > 0 ? x : -x;
}
inline int gcd(const int a, const int b) { return b ? gcd(b, a % b) : a; }
inline void getInv(int inv[], const int lim, const int MOD) {
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= lim; ++i)
    inv[i] = 1ll * inv[MOD % i] * (MOD - MOD / i) % MOD;
}
inline long long mulMod(const long long a, const long long b,
                        const long long mod) {
  return ((a * b - (long long)((long double)a / mod * b + 1e-8) * mod) % mod +
          mod) %
         mod;
}
}  // namespace IO
using namespace IO;
const int maxk = 100;
const int mod = 998244353;
const int phimod = mod - 1;
inline int qkpow(int a, int n) {
  int ret = 1;
  for (; n > 0; n >>= 1, a = 1ll * a * a % mod)
    if (n & 1) ret = 1ll * ret * a % mod;
  return ret;
}
map<int, int> MP;
inline int bsgs(const int a, const int x, const int p) {
  int m = ceil(sqrt(p)), base = 1, tmp = 1;
  for (signed i = (1), i_end_ = (m); i <= i_end_; ++i) {
    base = 1ll * base * a % p;
    MP[1ll * base * x % p] = i;
  }
  for (signed i = (1), i_end_ = (m); i <= i_end_; ++i) {
    tmp = 1ll * tmp * base % p;
    if (MP[tmp]) return i * m - MP[tmp];
  }
  return -1;
}
struct matrix {
  int a[maxk + 5][maxk + 5], n, m;
  matrix(const int N = 0, const int M = 0) : n(N), m(M) {
    memset(a, 0, sizeof a);
  }
  inline void origin(const int N) {
    (*this) = matrix(N, N);
    for (signed i = (1), i_end_ = (n); i <= i_end_; ++i) a[i][i] = 1;
  }
  inline matrix operator*(const matrix rhs) const {
    if (m != rhs.n) {
      cout << "operator:>Error\n";
      exit(0);
    }
    matrix ret(n, rhs.m);
    for (signed i = (1), i_end_ = (n); i <= i_end_; ++i)
      for (signed j = (1), j_end_ = (m); j <= j_end_; ++j)
        if (a[i][j])
          for (signed k = (1), k_end_ = (rhs.m); k <= k_end_; ++k)
            ret.a[i][k] =
                (ret.a[i][k] + 1ll * a[i][j] * rhs.a[j][k] % phimod) % phimod;
    return ret;
  }
  inline void print() {
    cout << "Print:>n == " << n << ", m == " << m << '\n';
    for (signed i = (1), i_end_ = (n); i <= i_end_; ++i) {
      for (signed j = (1), j_end_ = (m); j <= j_end_; ++j)
        cout << a[i][j] << " ";
      cout << '\n';
    }
  }
  inline friend matrix qkpow(matrix a, int n) {
    if (a.n != a.m) {
      cout << "qkpow:>Error\n";
      exit(0);
    }
    matrix ret;
    ret.origin(a.n);
    for (; n > 0; n >>= 1, a = a * a)
      if (n & 1) ret = ret * a;
    return ret;
  }
};
int k, b[maxk + 5], n, m;
matrix ori, acc;
inline void Init() {
  cin >> k;
  for (signed i = (1), i_end_ = (k); i <= i_end_; ++i)
    cin >> b[i], b[i] %= phimod;
  cin >> n >> m;
}
inline int Get_exponent() {
  ori = matrix(1, k), acc = matrix(k, k);
  ori.a[1][k] = 1;
  for (signed i = (2), i_end_ = (k); i <= i_end_; ++i) acc.a[i][i - 1] = 1;
  for (signed i = (1), i_end_ = (k); i <= i_end_; ++i)
    acc.a[i][k] = b[k - i + 1];
  ori = ori * qkpow(acc, n - k);
  return ori.a[1][k];
}
int exgcd(const int a, const int b, int& x, int& y) {
  if (!b)
    return x = 1, y = 0, a;
  else {
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
  }
}
signed main() {
  Init();
  int exp = Get_exponent();
  int x = bsgs(qkpow(3, exp), m, mod);
  if (x == -1)
    cout << "-1\n";
  else
    cout << qkpow(3, x) << '\n';
  return 0;
}