お詫び

出題時の制約下では，特定の解法を除き非本質な点で不正解となることが多いことや，非本質な実装を問うようなものになっていた為，この問題に対する取り組みやすさを考慮して制約の変更・テストケースの入れ替えを行いました。(2021/02/05/21:11時点でテストケースの追加は未完です。) ご迷惑をおかけして本当に申し訳ありませんでした。

問題文

長さ$\ K\ $の数列$\ A\ $が与えられます。全ての要素が数列$\ A\ $の要素からなり，連続する$2$要素が異なるような長さ$\ N\ $の数列を考えます。
このような数列のうち，すべての要素の$bitwise\ xor$が$\ X\ $以上$\ Y\ $以下となるようなものの総数を$998244353$で割ったあまりを求めてください。

入力

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

(2021/02/01/01:54) 制約を変更しました。

• $N$ は $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$
• $i\neq j\ $ならば $A_i\neq A_j$
• 入力はすべて整数

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

• $1\le K\le 2^{18}$
• $K^N$に関する制約はない

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

出力

答えをを出力して，最後に改行してください。

サンプル

2 3 5 7
1 2 4

4

4 5 1 4
5 1 2 8 10

78