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

			public class codeforces
			{	
				public static long M = 1000000007;
				public static TreeSet<Integer> adj[];
			
				public static void main(String[] args)
				{
					InputReader in = new InputReader(System.in);
					PrintWriter pw = new PrintWriter(System.out);
					
					int k = in.nextInt();
					long[] b = new long[k];
					long p = 998244353;
					for(int i=0;i<k;i++)
						b[i] = in.nextLong();
					long[][] mat = new long[k][k];
					long n = in.nextLong();
					long m = in.nextLong();
					for(int i=0;i<k;i++)
						mat[0][i] = b[i];
					for(int i=1;i<k;i++)
						mat[i][i-1] = 1;
					mat = matrixpower(mat, n-k, p);
					long q = mat[0][0], g = 3, l = modularExponentiation(g, q, p), sqrt_p = (int)Math.sqrt(p);
					HashMap<Long, Long> map = new HashMap<>();
					for(long i=0;i<=sqrt_p;i++)
					{
						long key = modInverse(modularExponentiation(l, i, p), p);
						map.put((m*key)%p, i);
					}
					long ans = -1, y = -1;
					for(long i=0;i<=sqrt_p;i++)
					{
						long key = modularExponentiation(l, (i*sqrt_p)%(p-1), p);
						if(map.containsKey(key))
						{
							y = (i*sqrt_p)%(p-1) + map.get(key);
							y %= p-1;
						}
					}
					if(y != -1)
						ans = modularExponentiation(g, y, p);
					pw.println(ans);
					pw.flush();
					pw.close();
				}
				
				public static long[][] matrixpower(long[][] mat, long n, long p)
				{
					int r = mat.length;
					long[][] ans = new long[r][r];
					
					for(int i=0;i<r;i++)
						ans[i][i] = 1;
					
					while(n > 0)
					{
						if(n%2 == 1)
							ans = matrixmultiply(ans, mat, p);
						mat = matrixmultiply(mat, mat, p);
						n /= 2;
					}
					
					return ans;
				}
				
				public static long[][] matrixmultiply(long[][] M1, long[][] M2, long p)
				{
					int m1 = M1.length, m2 = M2[0].length;
					long[][] ans = new long[m1][m2];
					
					for(int i=0;i<m1;i++)
					{
						for(int j=0;j<m2;j++)
						{
							for(int k=0;k<M2.length;k++)
							{
								ans[i][j] += M1[i][k]*M2[k][j];
								if(ans[i][j] >= p-1)
									ans[i][j] %= p-1;
							}
						}
						//System.out.println(Arrays.toString(ans[i]));
					}
					return ans;
				}
				
				public static long prime(long nth) {
				    
				    long num, count, i;
				    num=1;
				    count=0;
				 
				    while (count < nth){
				      num=num+1;
				      for (i = 2; i <= num; i++){ //Here we will loop from 2 to num
				        if (num % i == 0) {
				          break;
				        }
				      }
				      if ( i == num){//if it is a prime number
				        count = count+1;
				      }
				    }
				    return num;
				  }
			  
				
				public static int[] suffle(int[] a,Random gen)
				{
					int n = a.length;
					for(int i=0;i<n;i++)
					{
						int ind = gen.nextInt(n-i)+i;
						int temp = a[ind];
						a[ind] = a[i];
						a[i] = temp;
					}
					return a;
				}
				
				public static long modularExponentiation(long x,long n,long M)
				{
				    long result=1;
				    while(n>0)
				    {
				        if(n % 2 ==1)
				            result=(result * x)%M;
				        x=(x*x)%M;
				        n=n/2;
				    }
				    return result;
				}
				
				public static long modInverse(long A,long M)
				{
				    return modularExponentiation(A,M-2,M);
				}
				
				public static int BinarySearch_l(long[] a, long k)
				{
					int n = a.length;
					int i = 0, j = n-1;
					int mid = 0;
					
					if(k - a[n-1] > 0)
						return n;
					else
					{
						while(j - i > 0)
						{
							mid = (i+j)/2;
							
							if(k - a[mid] > 0)
								i = mid + 1;
							else
								j = mid;
						}
					}
					
					return i;
				}
				
				public static int BinarySearch_r(long[] a, long k)
				{
					int n = a.length;
					int i = 0, j = n-1;
					int mid = 0;
					
					if(k - a[0] < 0)
						return -1;
					else
					{
						while(j - i > 0)
						{
							mid = (int)Math.ceil((double)(i+j)/2);
							
							if(k - a[mid] >= 0)
								i = mid;
							else
								j = mid - 1;
						}
					}
					
					return i;
				}
				public static long fact(long n, long M)
				{
					long ans = 1;
					
					for(long i=n;i>0;i--)
					{
						ans = (ans*i)%M;
					}
					
					return ans;
				}
				
			/*	public static void DFS(int sourse)
				{
					int count = 0;
					visited[sourse] = true;
					
					for(int u : adj[sourse])
					{
						if(!visited[u])
						{
							DFS(u);
						}
					}
					
					
				}*/
				
				public static ArrayList Divisors(int n)
				{
				    ArrayList<Integer> div = new ArrayList<>();
				    
				    for (int i=1; i<=Math.sqrt(n); i++)
				    {
				        if (n%i == 0)
				        {
				        	div.add(i);
				                
				            if(n/i != i)
				            	div.add(n/i);
				        }
				    }
				    return div;
				}
			
				public static long GCD(long a,long b)
				{
					if(b==0)
						return a;
					else
						return GCD(b,a%b);
				}
				
				public static long LCM(long a,long b)
				{
					return (a*b)/GCD(a, b);
				}
				
				static class pair implements Comparable<pair>
				{
					Integer x, y;
					pair(int x,int y)
					{
						this.x=x;
						this.y=y;
					}
					
					public int compareTo(pair o) {
						int result = x.compareTo(o.x);
						if(result==0)
							result = y.compareTo(o.y);
						
						return result;
					}  
					
					public String toString()
					{
						return x+" "+y;
					}
					
					public boolean equals(Object o)
					{
						if (o instanceof pair)
					    {
							pair p = (pair)o;
							return p.x - x == 0 && p.y - y == 0 ;
						}
						return false;
					}
					
					public int hashCode()
					{
						return new Long(x).hashCode()*31 + new Long(y).hashCode();
					}
				}
				
				static class InputReader 
				{
					 
					private final InputStream stream;
					private final byte[] buf = new byte[8192];
					private int curChar, snumChars;
					private SpaceCharFilter filter;
			 
					public InputReader(InputStream stream) 
					{
						this.stream = stream;
					}
			 
					public int snext() 
					{
						if (snumChars == -1)
							throw new InputMismatchException();
						if (curChar >= snumChars) 
						{
							curChar = 0;
							try 
							{
								snumChars = stream.read(buf);
							} 
							catch (IOException e) 
							{
								throw new InputMismatchException();
							}
							if (snumChars <= 0)
								return -1;
						}
						return buf[curChar++];
					}
			 
					public int nextInt() 
				    {
						int c = snext();
						while (isSpaceChar(c)) 
						{
							c = snext();
						}
						int sgn = 1;
						if (c == '-')
					    {
							sgn = -1;
							c = snext();
						}
						int res = 0;
						do 
						{
							if (c < '0' || c > '9')
								throw new InputMismatchException();
							res *= 10;
							res += c - '0';
							c = snext();
						} while (!isSpaceChar(c));
						return res * sgn;
					}
			 
					public long nextLong()
				    {
						int c = snext();
						while (isSpaceChar(c)) 
						{
							c = snext();
						}
						int sgn = 1;
						if (c == '-') 
						{
							sgn = -1;
							c = snext();
						}
						long res = 0;
						do 
						{
							if (c < '0' || c > '9')
								throw new InputMismatchException();
							res *= 10;
							res += c - '0';
							c = snext();
						} while (!isSpaceChar(c));
						return res * sgn;
					}
			 
					public int[] nextIntArray(int n) 
					{
						int a[] = new int[n];
						for (int i = 0; i < n; i++) 
						{
							a[i] = nextInt();
						}
						return a;
					}
			 
					public String readString()
				    {
						int c = snext();
						while (isSpaceChar(c)) 
						{
							c = snext();
						}
						StringBuilder res = new StringBuilder();
						do 
						{
							res.appendCodePoint(c);
							c = snext();
						} while (!isSpaceChar(c));
						return res.toString();
					}
			 
					public String nextLine() 
					{
						int c = snext();
						while (isSpaceChar(c))
							c = snext();
						StringBuilder res = new StringBuilder();
						do 
						{
							res.appendCodePoint(c);
							c = snext();
						} while (!isEndOfLine(c));
						return res.toString();
					}
			 
					public boolean isSpaceChar(int c) 
					{
						if (filter != null)
							return filter.isSpaceChar(c);
						return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
					}
			 
					private boolean isEndOfLine(int c) 
					{
						return c == '\n' || c == '\r' || c == -1;
					}
			 
					public interface SpaceCharFilter
				    {
						public boolean isSpaceChar(int ch);
					}
				}
				
				static class CodeX {
		        public static void sort(long arr[]) {
		            merge_sort(arr, 0, arr.length - 1);
		        }
		
		        private static void merge_sort(long A[], long start, long end) {
		            if (start < end) {
		                long mid = (start + end) / 2;
		                merge_sort(A, start, mid);
		                merge_sort(A, mid + 1, end);
		                merge(A, start, mid, end);
		            }
		
		        }
		
		        private static void merge(long A[], long start,long mid, long end) {
		            long p = start, q = mid + 1;
		            long Arr[] = new long[(int)(end - start + 1)];
		            long k = 0;
		
		            for (int i = (int)start; i <= end; i++) {
		                if (p > mid)
		                    Arr[(int)k++] = A[(int)q++];
		
		                else if (q > end)
		                    Arr[(int)k++] = A[(int)p++];
		
		                else if (A[(int)p] < A[(int)q])
		                    Arr[(int)k++] = A[(int)p++];
		
		                else
		                    Arr[(int)k++] = A[(int)q++];
		            }
		            for (int i = 0; i < k; i++) {
		                A[(int)start++] = Arr[i];
		            }
		
		        }
		
		    }
			}