Problem
サイズ
n*m の長方形フィールドが指定されています。各セルには負でない整数が含まれています。 セル (1,1) からセル (
n,
m) へのパスの数を数えて、
1) 各セルから、フィールドを離れずに
down または
right にのみ移動できます。
2) パス上のすべての数値のビットごとの排他的
OR は、
k と等しくなければなりません。
指定されたフィールドに一致するパスの数を見つけます。
入力
最初の行には、3 つの整数
n、
m、および
k (1 <= n、m <= 20、0 <= k <= 10
18) - フィールドの高さと幅、および数値
k.
次の
n 行には、それぞれ
m 個の整数
ai,j が含まれています。ここで
j は
i 番目の行の - 番目の要素は
ai,j (0 <= a
i,j < ;= 1018).
インプリント
整数を 1 つ出力 - すべての条件を満たすパスの数。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
3 3 11
2 1 5
7 10 0
12 6 4
| 3 |
| 2 |
3 4 2
1 3 3 3
0 3 3 2
3 0 1 1
| 5 |