题目描述

给定两个大小分别为 $n$ 和 $m$ 的集合 $S$ 和集合 $T$，集合 $S$ 中的第 $i$ 个元素为 $s_i$（编号从 $1$ 到 $n$），集合 $T$ 中的第 $i$ 个元素为 $t_i$（编号从 $1$ 到 $m$）。保证集合 $S$ 内的元素互不相同、保证集合 $T$ 内的元素互不相同。

你需要求有多少个长度为 $L$ 的序列 $a$（下标从 $1$ 到 $L$）满足：

• $\forall i\in[1,L],a_i\in S$。
• 令 $d_i=a_1\oplus a_2\oplus a_3\ldots \oplus a_i$，那么 $\forall i\in[1,L],d_i\not\in T$。其中 $\oplus$ 代表按位异或运算。

输出方案数对 $998244353$ 取模的结果。

输入格式

第一行三个正整数 $n, m, L$ 分别表示集合 $S$ 和 $T$ 的大小，和一个正整数 $L$。

第二行 $n$ 个非负整数依次表示集合 $S$ 中的元素，保证元素互不相同。

第三行 $m$ 个非负整数依次表示集合 $T$ 中的元素，保证元素互不相同。

输出格式

输出一行一个非负整数，表示答案对 $998244353$ 取模的结果。

样例

样例 1

4 4 4
3 4 5 6
0 3 1 2

3

样例 2

6 6 7
4 10 6 8 2 30
2 11 12 8 22 24

13118

样例 3

见下发文件中的 randomxor/randomxor3.in 与 randomxor/randomxor3.ans。

样例 4

见下发文件中的 randomxor/randomxor4.in 与 randomxor/randomxor4.ans。

数据范围

对于所有测试点：$n \le 35, m \le 20, L \le 4000, s_i, t_i \le 10^9$。