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.*;

import java.util.*;

public class F {

	static final int MOD = 998244353 ; 
	
	static int [][] mat ;
	static int k  , A , B; 
	
	static int extendedGCD(int a, int b)
	{
		if(b == 0) { A = 1; B = 0; return a;  }
		int g = extendedGCD(b, a % b);
		int x1 = B;
		int y1 = A - a / b * B;
		A = x1; B = y1;
		return g ; 
	}
	
	static int phi(int x)
	{
		int ans = x ; 
		
		for(int i = 2 ; 1l * i * i <= x ; i++)
		{
			if(x % i != 0) continue ; 
			
			ans -= ans / i ; 
			
			while(x % i == 0 ) x /= i ;
		}
		
		if(x > 1) ans -= ans / x ; 
		
		return ans ;
		
	}
	
	static int [][] mult (int [][] x , int [][] y)
	{
		int [][] ans = new int [k][k] ; 
		
		for(int l = 0 ; l < k ; l++)
			for(int i = 0 ; i < k ; i++)
				for(int j = 0 ; j < k ; j++)
				{
					ans[i][j] += mult(x[i][l] , y[l][j], MOD - 1);
					ans[i][j] %= MOD - 1 ;
				}	
				
		
		return ans ; 
	}
	static int [][] matPow(int e)
	{
		int [][] ans = new int [k][k] ; 
		
		for(int i = 0 ; i < k ;i++)
			ans[i][i] = 1 ; 
		
		while(e > 0)
		{
			if((e & 1) != 0)
				ans = mult(ans , mat);
			
			mat = mult(mat, mat); 
			
			e /= 2 ; 
		}
		
		return ans ; 
		
	}
	static int mult(long a , int b , int MOD)
	{
		return (int)((1l * a * b) % MOD) ; 
	}
	
	static int modPow(int a, long e , int MOD)
	{
		int ans = 1 ;
		
		while(e > 0)
		{
			if((e & 1) != 0)
				ans = mult(ans, a, MOD) ; 
			
			a = mult(a, a, MOD);
			e /= 2 ; 	
		}
		return ans ; 
	}
	
	static int primitiveRoot()
	{
		
		int phi = MOD - 1 ; 
		int p = MOD - 1 ;
		
		ArrayList<Integer> divs = new ArrayList<>();
		
		for(int i = 2 ; 1l * i * i <= p ; i++)
		{
			if(p % i != 0) continue ; 
			
			divs.add(i) ; 
			
			while(p % i == 0 ) p /= i ; 
		}
		
		outer : 
		for(int ans = 2 ; ans <= MOD ; ans++)
		{
			
			for(int x : divs)
				if(modPow(ans, phi / x , MOD) == 1)
					continue outer ; 
				
			return ans ; 
		}
		
		return -1 ;
		
	}
	
	static long discreteLog(int g , int m , int gcd)
	{
		if(m == 1)return 0 ;
		
		int n = (int)Math.sqrt(MOD) + 1 , an = 1; 
		
		HashMap<Integer , Integer> map = new HashMap<>() ;  // values of a ^ pq -> p  
		
		for(int i = 0 ; i < n ; i++) an = mult(an, g, MOD) ;
		
		for(int p = 1 , curr = an ; p <= n ; p++ , curr = mult(curr, an, MOD)) map.put(curr, p);
		
		for(int q = 0 , curr = m ; q <= n ; q ++ , curr = mult(curr, g, MOD))
		{	
			Integer p = map.get(curr);
			
			if(p != null && ((1l * n * p - q) % gcd) == 0)return (1l * n * p - q)/gcd ; 
		}
		
		return -1 ; 
			
	}
	
	static int gcd(int a, int b)
	{
		return b == 0 ? a : gcd(b, a % b) ; 
	}
	
	public static void main(String[] args) throws Exception {

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		k = sc.nextInt() ; 
		
		int [] b = new int [k] ; 
		for(int i = 0 ; i < k ; i++)b[i] = sc.nextInt() ; 
		
		int n = sc.nextInt() , m = sc.nextInt(); 
		
		mat = new int [k][k] ; 
		
		for(int i = 0 ;i < k ;i++) mat[0][i] = b[i] % (MOD - 1); 
		for(int i = 0 ; i < k - 1; i++)mat[i + 1][i] = 1 ; 
		
		int [][] mm = matPow(n - k) ; 
		
//		for(int i = 0 ; i < k;i++)
//			System.out.println(Arrays.toString(mm[i]));
		
		int c = mm[0][0] ;
		int g = primitiveRoot() ; 
		
		if(g == -1) {System.out.println(-1);return;}
		
		int gcd = gcd(c , MOD - 1) ; 
//		System.out.println(c+" "+gcd);
		
		long hn = discreteLog(g, m , gcd); 
		
		if(hn == -1 ){System.out.println(-1);return;}
		
		// c * hx = hn (mod p - 1) -> c * hx + (p - 1) * k = hn , c * A + (p - 1) * B = gcd(c , p - 1) 
		extendedGCD(c / gcd , (MOD - 1) / gcd);
		
		long hk = (hn * A) % (MOD - 1) ; 
		
		if(hk < 0) hk += MOD - 1 ;
		
		
		out.println(modPow(g, hk, MOD));
		
		
		
		out.flush();
		out.close();

	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() throws Exception {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		int nextInt() throws Exception {
			return Integer.parseInt(next());
		}

		long nextLong() throws Exception {
			return Long.parseLong(next());
		}

		double nextDouble() throws Exception {
			return Double.parseDouble(next());
		}

	}

	static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}

}