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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.HashMap;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author beginner1010
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF {
        final int mod = 998244353;
        final int g = 3;

        int add(int a, int b, int mod) {
            long ans = a;
            ans += b;
            ans %= mod;
            if (ans < 0) ans += mod;
            return (int) ans;
        }

        int mul(int a, int b, int mod) {
            long ans = a;
            ans *= b;
            ans %= mod;
            if (ans < 0) ans += mod;
            return (int) ans;
        }

        int pow(int a, int b, int p) {
            if (b == 0) return 1;
            if ((b & 1) == 1) return mul(a, pow(a, b - 1, p), p);
            else {
                int aux = pow(a, b >> 1, p);
                return mul(aux, aux, p);
            }
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int k = in.nextInt();
            Matrix A = new Matrix(k);
            for (int i = 0; i < k; i++) {
                A.mat[0][i] = in.nextInt();
                if (i > 0)
                    A.mat[i][i - 1] = 1;
            }
            int n = in.nextInt();
            int[][] mat = A.pow(A.mat, n - k, mod - 1);
            int fn = in.nextInt();
            NumberTheory nt = new NumberTheory();
            int hn = nt.shank(g, fn, mod);
            if (hn == -1) {
                out.println(-1);
                return;
            }
            int hk = nt.congurence(mat[0][0], hn, mod - 1);
            if (hk == -1) {
                out.println(-1);
                return;
            }
            out.println(pow(g, hk, mod));
        }

        class Matrix {
            int[][] mat;
            int n;

            Matrix(int _n) {
                this.n = _n;
                mat = new int[n][n];
            }

            int[][] multiply(int[][] a, int[][] b, int mod) {
                int[][] c = new int[a.length][b[0].length];
                for (int i = 0; i < a.length; i++) {
                    for (int j = 0; j < b[0].length; j++) {
                        for (int k = 0; k < b.length; k++) {
                            c[i][j] = add(c[i][j], mul(a[i][k], b[k][j], mod), mod);
                        }
                    }
                }
                return c;
            }

            int[][] pow(int[][] base, int b, int mod) {
                if (b == 1) return base;
                if ((b & 1) == 1) return multiply(base, pow(base, b - 1, mod), mod);
                else {
                    int[][] aux = pow(base, b >> 1, mod);
                    return multiply(aux, aux, mod);
                }
            }

        }

        class NumberTheory {
            int gcd(int a, int b) {
                return b == 0 ? a : gcd(b, a % b);
            }

            int[] exGCD(int a, int b) {
                if (b == 0) return new int[]{a, 1, 0};
                int[] res = exGCD(b, a % b);
                int g = res[0];
                int x = res[2];
                int y = res[1] - (a / b) * res[2];
                return new int[]{g, x, y};
            }

            int congurence(int a, int b, int p) {
                if (b == 0) return 0;
                int g = gcd(a, p);
                if ((b % g) != 0) return -1;
                int aPrime = a / g;
                int bPrime = b / g;
                int pPrime = p / g;
                int[] ansEq = exGCD(aPrime, pPrime);
                int x = mul(ansEq[1], 1, p);
                x = mul(x, bPrime, p);
                return x;
            }

            int shank(int g, int a, int p) {
                HashMap<Integer, Integer> map = new HashMap<>();
                int sqrt = (int) (Math.sqrt(p) + 1.0);
                int left = 1;
                for (int i = 0; i <= sqrt; i++) {
                    map.put(left, i);
                    left = mul(left, g, p);
                }
                int multiplier = pow(g, mul(p - 2, sqrt, p - 1), p); // little fermat's theorem
                int current = a;
                for (int i = 0; i <= sqrt; i++) {
                    if (map.containsKey(current)) {
                        return map.get(current) + i * sqrt;
                    }
                    current = mul(current, multiplier, p);
                }
                return -1;
            }

        }

    }

    static class InputReader {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputStream stream;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isWhitespace(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isWhitespace(c));
            return res * sgn;
        }

    }
}