問題一覧 > 通常問題

No.1210 XOR Grid

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 74
作問者 : simasima_71simasima_71 / テスター : RhoRho
4 ProblemId : 4846 / 出題時の順位表
問題文最終更新日: 2020-08-29 23:00:40

問題文

縦 $N$ 行横 $M$ 列のマス目があります。また、 $N$ 個の整数 $A_1,\ A_2,\dots\ A_N$ と $M$ 個の整数 $B_1,\ B_2, \dots\ B_M$ が与えられます。
この全てのマスに$2^X$未満の非負整数を書きます。その結果、 $i$ 行目の全ての数のXORが $A_i$ 、$j$ 列目の全ての数のXORが $B_j$ になるようにしたいです。
このような書き込み方は何通りありますか? $10^9+7$ で割った余りを出力してください。

入力

$N\ M\ X$
$A_1\ \dots\ A_N$
$B_1\ \dots\ B_M$

入力は全て整数
$1 \le N{,}M \le 200000=2 \times 10^5$
$1 \le X \le 60$
$0 \le A_i{,}B_j < 2^X$

出力


書き込み方を $({10}^9+7)$ で割った余りを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
2 2 1
1 0
0 1
出力
2


$1$行目に $(1,0)$、$2$行目に $(1,1)$
$1$行目に $(0,1)$、$2$行目に $(0,0)$
この2通りの書き込み方があります。

サンプル2
入力
1 1 60
12345
67890
出力
0


書き込み方が存在しないときは$0$を出力してください。

サンプル3
入力
10 8 60
998 977 811 700 609 444 915 39 578 800
941 749 221 649 397 613 804 883
出力
542426066


$({10}^9+7)$で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。