410194: GYM103973 D Random

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<2^k)$$$ such that $$$\text{rand}(x,A)=x$$$.

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|<k)$$$.

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

3 5
2 3 -4

2

0 3

8