D. Random
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Walk Alone has a special random number generator, the pseudocode of which is as follows:

uintk rand(uintk x, int A[]) {
    for (int i = 0; i < A.size(); ++i) {
        if (A[i] >= 0) x ^= x << A[i];
        else x ^= x >> -A[i];
    }
    return x;
}

Here 'uintk' denotes the type of unsigned integers with $$$k$$$ binary bits ('bitset<k>' in C++).

Given an array $$$A$$$ and an integer $$$k$$$, Walk Alone wants to know the number of integer $$$x\ (0\le x \lt 2^k)$$$ such that $$$\text{rand}(x,A)=x$$$.

Input

The first line contains two integers $$$n\ (0\le n\le 10^3)$$$ and $$$k\ (1\le k\le 10^3)$$$, the size of array $$$A$$$ and the length of type 'uintk' respectively.

The second line contains $$$n$$$ integers, the $$$i$$$-th of which is $$$A_i\ (|A_i| \lt k)$$$.

Output

Print the number of $$$x$$$ modulo $$$998\ 244\ 353$$$.

Examples
Input
3 5
2 3 -4
Output
2
Input
0 3
Output
8