No.1210 XOR Grid
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 105
作問者 :
simasima_71
/ テスター :
Rho
タグ : / 解いたユーザー数 105
作問者 :
simasima_71
/ テスター :
Rho
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。