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

public class Main {

    void solve() {
        k=ni();
        b=new int[k+1];
        for(int i=1;i<=k;i++) b[i]=ni();
        long n=ni(),m=ni();
        long Mat[][]=new long[k+1][k+1];
        for(int i=1;i<=k;i++) Mat[1][i]=b[i];
        for(int i=2;i<=k;i++){
            Mat[i][i-1]=1;
        }
        Mat=pow(Mat,n-k,M-1);
        long B=Mat[1][1];

        long y=babyStepGiantStepAlgorithm(modpow(g,B,M),m,M);
        if(y==-1){
            pw.println("-1");
            return;
        }
        long ans=modpow(g,y,M);
        pw.println(ans);




    }
    int k;
    int b[];
    int g=5;
    long [][] pow(long A[][],long x,long mod){
        if(x==0){
            long C[][]=new long[k+1][k+1];
            for(int i=1;i<=k;i++) C[i][i]=1;
            return C;
        }else if(x==1){
            return A;
        }
        long C[][]=pow(A,x/2,mod);
        C=mul(C,C,mod);
        if((x&1)>0) return mul(A,C,mod);
        return C;

    }
    long [][] mul(long A[][],long B[][],long mod){
        long C[][]=new long[k+1][k+1];
        for(int i=1;i<=k;i++){
            for(int j=1;j<=k;j++){
                for(int kk=1;kk<=k;kk++){
                    C[i][j]=add(C[i][j],mul(A[i][kk],B[kk][j],mod),mod);
                }
            }
        }
        return C;
    }


    long modpow(long a, long b,long M)
    {
        long r=1;
        while(b>0)
        {
            if((b&1)>0) r=mul(r,a,M);
            a=mul(a,a,M);
            b>>=1;
        }
        return r;
    }
    long mul(long x,long y,long M){
        x*=y;
        if(x>=M) x%=M;
        return x;
    }
    long add(long x,long y,long M){
        x+=y;
        if(x>=M) x-=M;
        return x;
    }
    long sub(long x,long y,long M){
        x-=y;
        if(x<0) x+=M;
        return x;
    }
    long babyStepGiantStepAlgorithm(long a,long b,long m){
            long n=(long)Math.sqrt(m);
            long an=modpow(a,n,m);
            long pMax=(long)Math.ceil(m*1.0/n);
            long qMax=n;
        TreeMap<Long, Long> mp = new TreeMap<>();
        long curr=1;
            for(long p=1;p<=pMax;p++){
                curr=curr * an % m;
                mp.put(curr,p);
            }
            long aq=1;
        for(long q=0;q<=qMax;q++){
            long d=aq * b % m;
            if(mp.lowerKey(d+1)!=null){
                long c=mp.lowerKey(d+1);
                if(d==c){
                    long p=mp.get(c);
                    return n*p-q;
                }
            }
            aq=aq* a % m;
        }
        return -1;

    }



    long M = 998244353;
    InputStream is;
    PrintWriter pw;
    String INPUT = "";

    void run() throws Exception {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        pw = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        pw.flush();
        if (!INPUT.isEmpty()) tr(System.currentTimeMillis() - s + "ms");

    }

    public static void main(String[] args) throws Exception {
        new Main().run();
    }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++) map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }

        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private void tr(Object... o) {
        if (INPUT.length() > 0) System.out.println(Arrays.deepToString(o));
    }

}