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 static java.lang.Math.*;
// import java.math.BigInteger;
import java.io.*;
import java.util.*;

// solution code is in entryPoint()

public class RecSeq {
    final static long mod = 998244353l;
    final static long mod2 = mod - 1;
    final static long rootMod = 32500l;
    final static long omega = 3l;
    final static int maxn = 1_000_007;
    final static long infty = 1_000_000_009l;

    // final static boolean DEBUG = true;
    final static boolean DEBUG = false;

    static class Solver {

        TreeMap<Long, Long> p3;

        static long i3 = modexp(3, mod - 2);

        public long discreteLog(long x) {
            long a = modexp(i3, rootMod);
            long cp = 1l;
            for (long j = 0; ;j++) {
                long cur = (cp * x) % mod;
                cp = (cp * a) % mod;
                if (p3.containsKey(cur)) {
                    return (p3.get(cur) + rootMod * j) % mod2;
                }
            }
        }

        public void matrixMult(long[][] A, long[][] B, long[][] C) {
            int n = A.length;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    C[i][j] = 0l;
                    for (int k = 0; k < n; k++) {
                        C[i][j] = (C[i][j]  + (A[i][k] * B[k][j]) % mod2) % mod2;
                    }
                }
            }
        }

        public void copy(long[][] A, long[][] B) {
            int n = A.length;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    B[i][j] = A[i][j];
                }
            }
        }

        public void matrixExpo(long[][] A, long ex) {
            int n = A.length;
            long[][] Z = new long[n][n];
            long[][] T = new long[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    Z[i][j] = (i == j) ? 1 : 0;
                }
            }

            while (ex > 0) {
                if ((ex & (1l)) > 0) {
                    matrixMult(Z, A, T);
                    copy(T, Z);
                }
                matrixMult(A, A, T); copy(T, A);
                ex >>= 1l;
            }

            copy(Z, A);
        }

        long[] g;

        public void entryPoint() {

            p3 = new TreeMap<Long, Long>();

            p3.put(1l, 0l);
            long last = 1l;

            for (long j = 1; j < rootMod; j++) {
                last = (last * 3) % mod;
                p3.put(last, j);
            }

            int k = in.gi();
            long[][] A = new long[k][k];

            for (int i = 0; i < k - 1; i++) {
                for (int j = 0; j < k; j++) {
                    if (j == i + 1) A[i][j] = 1;
                    else A[i][j] = 0;
                }
            }

            for (int j = 0; j < k; j++) {
                A[k - 1][k - 1 - j] = in.gl() % mod2;
            }

            // for (int i = 0; i < k; i++) {
            //     for (int j = 0; j < k; j++) {
            //         print(A[i][j], " ");
            //     }
            //     // println(" ");
            // }

            // println("---");

            long n = in.gl(), m = discreteLog(in.gl()); 

            matrixExpo(A, n - k);

            // println("?", m);

            // for (int i = 0; i < k; i++) {
            //     for (int j = 0; j < k; j++) {
            //         print(A[i][j], " ");
            //     }
            //     println(" ");
            // }


            long v = A[k - 1][k - 1];

            if (v == 0 && m == 0) {
                println(1); return;
            }

            if (v == 0) {
                println(-1); return;
            }

            long md2 = mod2;

            long g = gcd(md2, v);
            if (m % g != 0) {
                println(-1); return;
            }
            v /= g; md2 /= g; m /= g; v %= md2;

            long alpha = (extEuc(md2, v).S * m) % md2;
            alpha = (alpha + md2) % md2;

            verify(alpha >= 0);

            println(modexp(3, alpha));
        }


        PrintWriter out;
        FastInput in;
        Random random_source;

        final static long modexp(long x, long ex) {
            long ans = 1l;
            for (; ex > 0; ex >>= 1l, x = (x * x) % mod) {
                if ((ex & (1l)) > 0) ans = (ans * x) % mod;
            }
            return ans;
        }

        static long gcd(long x, long y) {
            while (y > 0) {
                long t = x % y;
                x = y; y = t;
            }
            return x;
        }

        static LongPair extEuc(long x, long y) {
            if (y > x) return extEuc(y, x).swap();
            if (y == 0) return new LongPair(1l, 0l);
            long r = x / y;
            LongPair sol = extEuc(y, x % y);
            long a = sol.F, b = sol.S;
            sol = new LongPair(b, (a - (r * b) % mod2) % mod2);
            return sol;
        }

        // Random numbers

        void initRandom(Long seed) {
            random_source = new Random(seed);
        }

        void initRandom() {
            random_source = new Random(System.currentTimeMillis());
        }

        int rand(int bound) { // [0..bound)
            return random_source.nextInt(bound);
        }

        // Convenience functions

        static void debug(Object... obj) {
            if (DEBUG) {
                System.out.print("# ");
                for (Object o : obj) {
                    System.out.print(o.toString());
                    System.out.print(" ");
                }
                System.out.println("");
                System.out.flush();
            }
        }

       
        static String a2s(Object[] A) {
            return Arrays.toString(A);
        }

        static String a2s(int[] A) {
            return Arrays.toString(A);
        }

        static String a2s(long[] A) {
            return Arrays.toString(A);
        }


        void flush() {
            out.flush();
        }

        void print(Object... obj) {
            for (Object o : obj) {
                out.print(o.toString());
            }
        }

        void println(Object... obj) {
            for (Object o : obj) {
                out.print(o.toString());
            }
            out.println("");
        } 

        static void verify(boolean check) {    // equivalent to assert
            if (!check) {
                throw new RuntimeException("Verification error");
            }
        }

        static void reverse(long[] A, int l, int r) {
            int i = l, j = r - 1;
            while (i < j) {
                long t = A[i];
                A[i] = A[j];
                A[j] = t;
                i++; j--;
            }
        }

        static void reverse(int[] A, int l, int r) {
            int i = l, j = r - 1;
            while (i < j) {
                int t = A[i];
                A[i] = A[j];
                A[j] = t;
                i++; j--;
            }
        }

        // Measure time 

        long initTime;

        public void startWatch() {
            if (DEBUG) {
                initTime = System.nanoTime();
            }
        }

        public void endWatch() {
            if (DEBUG) {
                long current = System.nanoTime();
                long diff = current - initTime;
                long memory = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
                println("(Time: ", (double)diff / 1e9, ", Memory: ", memory/1000, "K)");            
            }
        }

        // Solver class constructor

        Solver(PrintWriter out, FastInput in) {
            this.out = out; this.in = in;
        }
    }

    public static void main(String args[]) {
        FastInput in = new FastInput(System.in);
        PrintWriter out = new PrintWriter(System.out);
        Solver solver = new Solver(out, in);
        solver.startWatch();
        solver.entryPoint();
        solver.endWatch();
        out.close();
    }
    
    static class FastInput {
        BufferedReader reader;
        StringTokenizer tok;

        public FastInput(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tok = null;
        }

        public String next() {
            while (tok == null || !tok.hasMoreTokens()) {
                try {
                    tok = new StringTokenizer(reader.readLine());
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            return tok.nextToken();
        }

        public int gi() {
            return Integer.parseInt(next());
        }

        public long gl() {
            return Long.parseLong(next());
        }

        public double gf() {
            return Double.parseDouble(next());
        }
    }

    static class Pair<A extends Comparable<A>, B extends Comparable<B>>
            implements Comparable<Pair<A, B>> {
        A F;
        B S;

        Pair(A x, B y) {
            F = x; S = y;
        }

        public boolean equals(Pair<A, B> oth) {
            return this.compareTo(oth) == 0;    
        }

        public int compareTo(Pair<A, B> Q) {
            if (this.F.compareTo(Q.F) == 0) {
                return this.S.compareTo(Q.S);
            } else {
                return this.F.compareTo(Q.F);
            }
        }

        public String toString() {
            return new StringBuilder("{")
                    .append(F.toString())
                    .append(", ")
                    .append(S.toString())
                    .append("}")
                    .toString();
        }
    }

    static class Edge<T> {
        int from; int to; 
        T extra;

        Edge(int from, int to) {
            this.from = from; this.to = to;
        }

        Edge(int from, int to, T extra) {
            this.from = from; this.to = to; this.extra = extra;
        }
    }

    static class Graph<T> {

        ArrayList<ArrayList<Edge<T>>> G;
        int size;
        boolean directed;

        Graph(int n, boolean directed) {
            this.directed = directed;
            G = new ArrayList<>();
            for (int j = 0; j <= n; j++) {
                G.add(new ArrayList<>());
            }
            this.size = n;
        }

        void addEdge(int x, int y) {
            G.get(x).add(new Edge<>(x, y));
            if (!directed) {
                G.get(y).add(new Edge<>(y, x));
            }
        }

        void addEdge(int x, int y, T extra) {
            G.get(x).add(new Edge<>(x, y, extra));
            if (!directed) {
                G.get(y).add(new Edge<>(y, x, extra));
            }
        }

        ArrayList<Edge<T>> adjacent(int x) {
            return G.get(x);
        }
    }

    static class LongPair implements Comparable<LongPair> {
        Long F;
        Long S;

        LongPair(Long x, Long y) {
            F = x; S = y;
        }

        public boolean equals(LongPair oth) {
            return this.compareTo(oth) == 0;    
        }

        public int compareTo(LongPair Q) {
            if (this.F.compareTo(Q.F) == 0) {
                return this.S.compareTo(Q.S);
            } else {
                return this.F.compareTo(Q.F);
            }
        }

        public LongPair swap() {
            return new LongPair(S, F);
        }

        public String toString() {
            return new StringBuilder("{")
                    .append(F.toString())
                    .append(", ")
                    .append(S.toString())
                    .append("}")
                    .toString();
        }
    }

    static class IntPair implements Comparable<IntPair> {
        Integer F;
        Integer S;

        IntPair(Integer x, Integer y) {
            F = x; S = y;
        }

        public boolean equals(IntPair oth) {
            return this.compareTo(oth) == 0;    
        }

        public int compareTo(IntPair Q) {
            if (this.F.compareTo(Q.F) == 0) {
                return this.S.compareTo(Q.S);
            } else {
                return this.F.compareTo(Q.F);
            }
        }

        public String toString() {
            return new StringBuilder("{")
                    .append(F.toString())
                    .append(", ")
                    .append(S.toString())
                    .append("}")
                    .toString();
        }
    }
}