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.util.stream.IntStream;
import java.util.Arrays;
import java.util.function.LongBinaryOperator;
import java.util.HashMap;
import java.nio.charset.Charset;
import java.util.StringTokenizer;
import java.util.Map;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.util.stream.LongStream;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.Collectors;
import java.io.UncheckedIOException;
import java.util.Objects;
import java.util.stream.Stream;
import java.io.Writer;
import java.security.AccessControlException;
import java.io.BufferedReader;
import java.util.regex.Pattern;
import java.io.InputStream;

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

    static class FLunarNewYearAndARecursiveSequence {
        private static final int MOD = 998244353;

        public void solve(int testNumber, LightScanner in, LightWriter out) {
            Debug.autoEnable();

            int k = in.ints();
            long[] b = in.longs(k);

            Vector iv = new Vector(k);
            for (int i = 0; i < k - 1; i++) {
                iv.set(i, 1);
            }

            int n = in.ints();
            long m = in.longs();

            Matrix mat = new Matrix(k, k);
            for (int i = 0; i < k; i++) mat.set(0, i, b[i]);
            for (int i = 1; i < k; i++) mat.set(i, i - 1, 1);

            ModMath mod1 = new ModMath(MOD - 1), mod2 = new ModMath(MOD);
            MatrixExponentiation exp = new MatrixExponentiation(
                    mat, 30, 0, mod1::add, mod1::prod
            );


            Matrix res = exp.power(n - k);


            long t = res.get(0, 0);
            long s = mod2.log(3, m);
            long d = IntMath.gcd(t, MOD - 1);
            if (s % d != 0) {
                out.ans(-1).ln();
                return;
            }
            long x = mod2.log(mod2.pow(3, t), m);
            out.ans(mod2.pow(3, x)).ln();

        }

    }

    static class LightWriter implements AutoCloseable {
        private final Writer out;
        private boolean autoflush = false;
        private boolean breaked = true;

        public LightWriter(Writer out) {
            this.out = out;
        }

        public LightWriter(OutputStream out) {
            this(new BufferedWriter(new OutputStreamWriter(out, Charset.defaultCharset())));
        }

        public LightWriter print(char c) {
            try {
                out.write(c);
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter print(String s) {
            try {
                out.write(s, 0, s.length());
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter ans(String s) {
            if (!breaked) {
                print(' ');
            }
            return print(s);
        }

        public LightWriter ans(long l) {
            return ans(Long.toString(l));
        }

        public LightWriter ans(int i) {
            return ans(Integer.toString(i));
        }

        public LightWriter ln() {
            print(System.lineSeparator());
            breaked = true;
            if (autoflush) {
                try {
                    out.flush();
                } catch (IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            }
            return this;
        }

        public void close() {
            try {
                out.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

    }

    static class Vec3i {
        public int x;
        public int y;
        public int z;

        public Vec3i(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vec3i vec3i = (Vec3i) o;
            return x == vec3i.x &&
                    y == vec3i.y &&
                    z == vec3i.z;
        }

        public int hashCode() {
            return Objects.hash(x, y, z);
        }

        public String toString() {
            return "(" + x + ", " + y + ", " + z + ")";
        }

    }

    static class Matrix {
        private final int n;
        private final int m;
        final long[][] contents;

        public Matrix(int n, int m, long[][] contents) {
            this.n = n;
            this.m = m;
            this.contents = contents;
        }

        public Matrix(int n, int m) {
            this(n, m, new long[n][m]);
        }

        public long get(int i, int j) {
            return contents[i][j];
        }

        public void set(int i, int j, long v) {
            contents[i][j] = v;
        }

        public Matrix product(Matrix other) {
            if (this.m != other.n) {
                throw new IllegalArgumentException("size mismatch");
            }
            Matrix res = new Matrix(n, other.m);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    for (int k = 0; k < other.m; k++) {
                        res.contents[i][k] += this.contents[i][j] * other.contents[j][k];
                    }
                }
            }
            return res;
        }

        public Matrix product(Matrix other, long zero, LongBinaryOperator add, LongBinaryOperator prod) {
            if (this.m != other.n) {
                throw new IllegalArgumentException("size mismatch");
            }
            Matrix res = new Matrix(n, other.m);
            ArrayUtil.fill(res.contents, zero);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    for (int k = 0; k < other.m; k++) {
                        res.contents[i][k] = add.applyAsLong(
                                res.contents[i][k],
                                prod.applyAsLong(this.contents[i][j], other.contents[j][k])
                        );
                    }
                }
            }
            return res;
        }

        public int getRows() {
            return n;
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Matrix matrix = (Matrix) o;
            return n == matrix.n &&
                    m == matrix.m &&
                    Arrays.equals(contents, matrix.contents);
        }

        public int hashCode() {
            int result = Objects.hash(n, m);
            result = 31 * result + Arrays.hashCode(contents);
            return result;
        }

        public String toString() {
            return Stream.of(contents).map(Arrays::toString).collect(Collectors.joining(System.lineSeparator()));
        }

        public static Matrix getUnitMatrix(int n) {
            Matrix unit = new Matrix(n, n);
            for (int i = 0; i < n; i++) {
                unit.contents[i][i] = 1L;
            }
            return unit;
        }

    }

    static class ModMath {
        private static final int DEFAULT_MOD = 1_000_000_007;
        private final long mod;

        public ModMath(long mod) {
            this.mod = mod;
        }

        public ModMath() {
            this(DEFAULT_MOD);
        }

        public long mod(long x) {
            x %= mod;
            return x < 0 ? x + mod : x;
        }

        public long inv(long x) {
            return mod(LongEuclidSolver.solve(x, -mod).x);
        }

        public long add(long x, long y) {
            return (x + y) % mod;
        }

        public long prod(long x, long y) {
            return (mod(x) * mod(y)) % mod;
        }

        public long pow(long x, long y) {
            if (y < 0) {
                return pow(inv(x), -y);
            } else if (y == 0) {
                return 1;
            } else if (y % 2 == 0) {
                long z = pow(x, y / 2);
                return (z * z) % mod;
            } else {
                return (x % mod) * pow(x, y - 1) % mod;
            }
        }

        public long log(long b, long x) {
            long m = (long) Math.ceil(Math.sqrt(mod));
            long pow = 1;
            Map<Long, Long> table = new HashMap<>();
            for (long j = 0; j < m; j++) {
                table.put(pow, j);
                pow *= b;
                pow %= mod;
            }
            long inv = pow(b, -m);
            long gamma = x % mod;
            for (int i = 0; i < m; i++) {
                if (table.containsKey(gamma)) {
                    return i * m + table.get(gamma);
                }
                gamma = gamma * inv % mod;
            }
            throw new RuntimeException("No solution found");
        }

    }

    static class Vector {
        final long[] contents;

        public Vector(long... contents) {
            this.contents = contents;
        }

        public Vector(int n) {
            this(new long[n]);
        }

        public void set(int i, long v) {
            contents[i] = v;
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vector vector = (Vector) o;
            return Arrays.equals(contents, vector.contents);
        }

        public int hashCode() {
            return Arrays.hashCode(contents);
        }

    }

    static final class ArrayUtil {
        private ArrayUtil() {
        }

        public static void fill(long[] a, long v) {
            Arrays.fill(a, v);
        }

        public static void fill(long[][] a, long v) {
            for (int i = 0; i < a.length; i++) {
                fill(a[i], v);
            }
        }

    }

    static class Vec3l {
        public long x;
        public long y;
        public long z;

        public Vec3l(long x, long y, long z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vec3i vec3i = (Vec3i) o;
            return x == vec3i.x &&
                    y == vec3i.y &&
                    z == vec3i.z;
        }

        public int hashCode() {
            return Objects.hash(x, y, z);
        }

        public String toString() {
            return "(" + x + ", " + y + ", " + z + ")";
        }

    }

    static class LongEuclidSolver {
        private LongEuclidSolver() {
        }

        public static Vec3l solve(long p, long q) {
            if (q == 0) {
                return new Vec3l(p, 1, p);
            }
            Vec3l vals = solve(q, p % q);
            long a = vals.y;
            long b = vals.x - (p / q) * a;
            return new Vec3l(a, b, vals.z);
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int ints() {
            return Integer.parseInt(string());
        }

        public long longs() {
            return Long.parseLong(string());
        }

        public long[] longs(int length) {
            return IntStream.range(0, length).mapToLong(x -> longs()).toArray();
        }

    }

    static final class IntMath {
        private IntMath() {
        }

        public static long gcd(long a, long b) {
            long t;
            while (a % b > 0) {
                t = b;
                b = a % b;
                a = t;
            }
            return b;
        }

    }

    static class Debug {
        private static final String DEBUG_PROPERTY = "debug";
        private static final String DEBUG_CALL_PATTERN = "^.+\\.debug\\((.+)\\);.*$";
        private static Pattern debugRegex;
        private static boolean enabled = false;
        private static String src;

        public static void enable(String s) {
            enabled = true;
            src = s;
            if (debugRegex == null) {
                debugRegex = Pattern.compile(DEBUG_CALL_PATTERN);
            }
        }

        public static boolean autoEnable() {
            try {
                String s = System.getProperty(DEBUG_PROPERTY);
                if (s != null) {
                    enable(s);
                    return true;
                }
            } catch (AccessControlException ex) {
                src = null;
            }
            return false;
        }

    }

    static class MatrixExponentiation {
        private static final int DEFAULT_SIZE = 64;
        private final int size;
        private final long zero;
        private final LongBinaryOperator add;
        private final LongBinaryOperator prod;
        private final Matrix[] exps;

        public MatrixExponentiation(Matrix e0, int size, long zero, LongBinaryOperator add, LongBinaryOperator prod) {
            this.size = size;
            this.zero = zero;
            this.add = add;
            this.prod = prod;
            exps = new Matrix[size];
            exps[0] = e0;
            for (int i = 1; i < size; i++) {
                exps[i] = exps[i - 1].product(exps[i - 1], zero, add, prod);
            }
        }

        public MatrixExponentiation(Matrix e0, long zero, LongBinaryOperator add, LongBinaryOperator prod) {
            this(e0, DEFAULT_SIZE, zero, add, prod);
        }

        public MatrixExponentiation(Matrix e0, int size) {
            this.size = size;
            zero = 0;
            add = null;
            prod = null;
            exps = new Matrix[size];
            exps[0] = e0;
            for (int i = 1; i < size; i++) {
                exps[i] = exps[i - 1].product(exps[i - 1]);
            }
        }

        public MatrixExponentiation(Matrix e0) {
            this(e0, DEFAULT_SIZE);
        }

        public Matrix power(long p) {
            Matrix res = Matrix.getUnitMatrix(exps[0].getRows());
            for (int i = 0; i < size; i++) {
                if (((1L << i) & p) == 0) {
                    continue;
                }
                if (add == null) {
                    res = res.product(exps[i]);
                } else {
                    res = res.product(exps[i], zero, add, prod);
                }
            }
            return res;
        }

    }
}