Apology

Under the constraints at the time of the contest, solutions other than certain specific ones often received wrong verdicts for non-essential reasons, and the problem ended up demanding non-essential implementation. Therefore, to make this problem easier to approach, we changed the constraints and replaced the test cases. (As of 2021/02/05/21:11, the addition of test cases has not been completed.) We are truly sorry for the inconvenience caused.

Problem Statement

You are given a sequence $\ A\ $ of length $\ K\ $. Consider sequences of length $\ N\ $ in which every element is an element of the sequence $\ A\ $ and any $2$ consecutive elements are different.
Among such sequences, find the number of those for which the $bitwise\ xor$ of all elements is at least $\ X\ $ and at most $\ Y\ $, modulo $998244353$.

Input

$N\ K\ X\ Y$
$A_1\ A_2\ ...\ A_K$

(2021/02/01/01:54) The constraints have been changed.

• $N$ is an even number satisfying $2\le N\le 30$
• $1\le K\le 1024$
• $0\le A_i < 1024$
• $0\le X\le Y < 1024$
• $K^N\le 2 \times 10^9$
• If $i\neq j\ $, then $A_i\neq A_j$
• All input values are integers

• $0\le A_i < 2^{18}$
• $0\le X\le Y < 2^{18}$

• $1\le K\le 2^{18}$
• There is no constraint on $K^N$

• $1\le N\le 10^{18}$

Output

Output the answer, followed by a newline.

Sample

2 3 5 7
1 2 4

4

4 5 1 4
5 1 2 8 10

78