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

class ModInt implements Comparable<ModInt>{
    static final private int MOD = 998244353;
    static final public ModInt ZERO = new ModInt(0);
    static final public ModInt ONE = new ModInt(1);
    static final public ModInt TWO = new ModInt(2);
    static final public ModInt TEN = new ModInt(10);
    static final public ModInt MINUSONE = new ModInt(-1);
 
    static final private ModInt[] fact, factInv;
    static{
        int max = 1000000;
        fact = new ModInt[max+1];
        factInv = new ModInt[max+1];
        fact[0] = ONE;
        for(int i=1; i<=max; i++) fact[i] = fact[i-1].mult(i);
        factInv[max] = fact[max].inverse();
        for (int i = max-1;i >= 0;-- i) factInv[i] = factInv[i + 1].mult(i + 1);
    }
 
 
    int num;
 
    public ModInt(int n){
        this.num = n%MOD;
        if(this.num<0) this.num += MOD;
    }
 
    public int compareTo(ModInt another){
        return Integer.compare(this.num, another.num);
    }
    public boolean equals(Object another){
        if(another instanceof ModInt) return compareTo((ModInt)another)==0;
        else return false;
    }
    public String toString(){
        return Integer.toString(num);
    }
 
    ModInt add(ModInt m){
        return new ModInt(this.num + m.num);
    }
    ModInt add(int m){
        m %= MOD;
        return new ModInt(this.num + m);
    }
    ModInt adds(ModInt... ms){
        int ret = this.num;
        for(ModInt m:ms){
            ret = (ret + m.num) % MOD;
        }
        return new ModInt(ret);
    }
    ModInt sub(ModInt m){
        return new ModInt(this.num - m.num);
    }
    ModInt sub(int m){
        return this.add(-m);
    }
    ModInt mult(ModInt m){
        long ret = this.num;
        ret = (ret * m.num)%MOD;
        return new ModInt((int) ret);
    }
    ModInt mult(int m){
        long ret = this.num;
        ret = (ret * m) % MOD;
        return new ModInt((int)ret);
    }
    ModInt mults(ModInt... ms){
        long ret = this.num;
        for(ModInt m:ms) ret = (ret * m.num) % MOD;
        return new ModInt((int) ret);
    }
    ModInt power(long exp){
        if(exp<0) return ZERO;
        long a = this.num;
        long ans = 1;
        while(exp>0){
            if(exp%2==1) ans = (ans * a) % MOD;
            a = (a*a)%MOD;
            exp /= 2;
        }
        return new ModInt((int) ans);
    }
    ModInt inverse(){
        return this.power(MOD-2);
    }
    ModInt divide(ModInt m){
        return this.mult(m.inverse());
    }
    ModInt divide(int m){ return this.divide(new ModInt(m)); }
    static ModInt factorial(int i){
        return fact[i];
    }
    static ModInt combination(int n, int r){
        if(n<0 || r<0 || n<r) return ZERO;
        return fact[n].mults(factInv[r], factInv[n-r]);
    }
    static ModInt permutation(int n, int r){
        if(n<0 || r<0 || n<r) return ZERO;
        return fact[n].mults(factInv[n-r]);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int S = sc.nextInt();
        int[] A = new int[N];
        for(int n=0; n<N; n++) A[n] = sc.nextInt();

        ModInt[][] dp = new ModInt[N+1][S+1];
        //dp[n][s] : with first n elements, 
        //how many pair (U,T) s.t. A subset T subset U and sum(U)==s?
        Arrays.fill(dp[0], ModInt.ZERO); dp[0][0]=ModInt.ONE;
        for(int n=1; n<=N; n++)  for(int s=0; s<=S; s++){
            dp[n][s] = dp[n-1][s].adds(dp[n-1][s], (s-A[n-1]>=0 ? dp[n-1][s-A[n-1]] : ModInt.ZERO));
        }
        System.out.println(dp[N][S]);

    }
}

