Given are a sequence of N positive integers A_1, A_2, \ldots, A_N and another positive integer S.
For a non-empty subset T of the set \\{1, 2, \ldots , N \\}, let us define f(T) as follows:


* f(T) is the number of different non-empty subsets \\{x_1, x_2, \ldots , x_k \\} of T such that A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.



Find the sum of f(T) over all 2^N-1 subsets T of \\{1, 2, \ldots , N \\}. Since the sum can be enormous, print it modulo 998244353.

Constraints

* All values in input are integers.
* 1 \leq N \leq 3000
* 1 \leq S \leq 3000
* 1 \leq A_i \leq 3000

Input

Input is given from Standard Input in the following format:


N S
A_1 A_2 ... A_N


Output

Print the sum of f(T) modulo 998244353.

Examples

Input

3 4
2 2 4


Output

6


Input

5 8
9 9 9 9 9


Output

0


Input

10 10
3 1 4 1 5 9 2 6 5 3


Output

3296



import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;



public class Main {

	static ArrayList<Integer>[] adjList;

	static final double EPS=1e-5;
	static int mod=998244353;
	static long[] fac;
	static long INF=(long)1e13;


	static int[] a;
	static int[][]memo;
	static int dp(int idx , int rem){
		if(rem<0)return 0;
		if(idx==a.length)return (rem==0)?1:0;
		if(memo[idx][rem]!=-1)return memo[idx][rem];
		if(rem==0)return memo[idx][rem]=(2*dp(idx+1,rem)%mod)%mod;
		int ans=(int) add(mul(2,dp(idx+1,rem)),dp(idx+1,rem-a[idx]));
		
		return memo[idx][rem]=ans;
	}

	public static void main(String[] args) throws IOException, InterruptedException {


		Scanner	sc = new Scanner(System.in);
		PrintWriter	pw =new PrintWriter(System.out);
//		long a=4294967297l;
//		long b=8589934593l;
//		long c=12884901890l;
//		pw.println(1.0*(c)/a);
	
		int n=sc.nextInt();
		int s=sc.nextInt();
		a=sc.nextIntArr(n);
		memo=new int[n+1][s+1];
		for(int[] ar:memo)
			Arrays.fill(ar,-1);
		pw.println( dp(0, s));

		pw.flush();
		pw.close();


	}



	static long powmod(long b,long e, int mod) {
		long ans=1;
		b%=mod;
		while(e>0) {
			if((e&1)==1)
				ans=(int)((ans*1l*b)%mod);
			e>>=1;
			b=(int)((b*1l*b)%mod);
		}
		return ans;
	}
	public static long add(long a, long b) {
		return (a+b)%mod;
	}
	public static long mul(long a, long b) {
		return ((a%mod)*(b%mod))%mod;
	}
	public static long ncr(int c, int r) {
		long ans= mul(fac[c],powmod(fac[c-r], mod-2, mod));
		ans=mul(ans,powmod(fac[r],mod-2,mod));
		return ans;
	}


	static class Pair implements Comparable<Pair>{
		int  x;int y;

		public Pair(int a,int b ) {
			this.x=a;y=b;
		}






		public int compareTo(Pair o) {
			return (x==o.x)?((y>o.y)?1:(y==o.y)?0:-1):((x>o.x)?1:-1);
		}


		@Override


		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}


		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pair other = (Pair) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}

	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
		public Scanner(String s) throws FileNotFoundException{	br = new BufferedReader(new FileReader(s));}

		public long[] nextLongArr(int n) throws IOException {
			long[] arr=new long[n];
			for(int i=0;i<n;i++)
				arr[i]=nextLong();
			return arr;
		}
		public int[] nextIntArr(int n) throws IOException {
			int[] arr=new int[n];
			for(int i=0;i<n;i++)
				arr[i]=nextInt();
			return arr;
		}
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine()," ,");
			return st.nextToken();
		}

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}


		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++) {
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
				if (sb.length() == 18) {
					res += Long.parseLong(sb.toString()) / f;
					sb = new StringBuilder("0");
				}
			}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	public 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;
		}
	}

}