E - Switching Communication Modes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は N 台の送信機を管理しています。それぞれの送信機には 1 から N までの番号がついています。

各送信機 i には2つの動作モードがあり、モード A では信号値 V_i を、モード B では信号値 W_i を出力します。ここで V_i , W_i はいずれも 0 以上の整数です。高橋君は最初に各送信機の動作モードを A か B のどちらかに設定します。一度設定したモードは以降変更できません。

送信機のうちいくつかを同時に稼働させると、それらの出力信号値の XOR（排他的論理和）が合成信号として得られます。稼働させる送信機の集合は自由に選べ、空集合を選んだ場合の合成信号は 0 とします。

高橋君は M 個の目標信号値 T_1, T_2, \ldots, T_M を持っています。高橋君は以下の手順で運用を行います：

  1. まず、各送信機の動作モードを A か B のどちらかに決定する（この決定は一度だけ行い、以降変更しない）。
  2. その後、 M 個の目標信号値それぞれについて、稼働させる送信機の部分集合を選び、その部分集合の合成信号が目標信号値と一致するようにする。目標信号値ごとに稼働させる部分集合は異なってよい。

高橋君は、 M 個の目標信号値の すべて を実現できるようにしたいです。すなわち、ステップ1で動作モードを適切に決めた上で、すべての目標信号値 T_j ( 1 \leq j \leq M ) に対して、合成信号がその値と一致するような送信機の部分集合が存在するようにしたいです。

このような動作モードの決定方法（各送信機が A か B かの 2^N 通りの割り当て）のうち、条件を満たすものの数を 10^9 + 7 で割った余りを求めてください。

制約

  • 1 \leq N \leq 15
  • 1 \leq M \leq 100
  • 0 \leq V_i \leq 2^{60} - 1 （ 1 \leq i \leq N ）
  • 0 \leq W_i \leq 2^{60} - 1 （ 1 \leq i \leq N ）
  • 0 \leq T_j \leq 2^{60} - 1 （ 1 \leq j \leq M ）
  • 入力はすべて整数である。

入力

N M
V_1 W_1
V_2 W_2
:
V_N W_N
T_1 T_2 \ldots T_M
  • 1 行目には、送信機の数を表す N 、目標信号値の数を表す M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各送信機の信号値が与えられる。
  • 1 + i 行目では、送信機 i のモード A での信号値 V_i とモード B での信号値 W_i が、スペース区切りで与えられる。
  • N + 2 行目には、 M 個の目標信号値 T_1, T_2, \ldots, T_M がスペース区切りで与えられる。

出力

条件を満たす動作モードの決定方法の数を 10^9 + 7 で割った余りを 1 行で出力せよ。

入力例 1

2 2
1 2
2 3
1 3

出力例 1

3

入力例 2

1 2
1 2
1 3

出力例 2

0

入力例 3

8 12
5 9
3 6
10 12
7 1
15 8
4 14
2 11
13 0
0 1 2 3 5 8 13 21 31 6 10 15

出力例 3

0

入力例 4

15 25
1 1099511627776
2 1099511627777
4 281474976710656
8 281474976710664
16 1125899906842624
32 1125899906842656
64 72057594037927936
128 72057594037928064
256 1152921504606846975
512 1152921504606846463
1024 123456789012345
2048 98765432109876
4096 555555555555555
8192 333333333333333
16384 777777777777777
0 1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 1099511627776 281474976710656 1125899906842624 72057594037927936 1152921504606846975 123456789012345 98765432109876 555555555555555 777777777777777

出力例 4

0

入力例 5

1 1
0 1152921504606846975
0

出力例 5

2

Score : 466 pts

Problem Statement

Takahashi manages N transmitters. The transmitters are numbered from 1 to N.

Each transmitter i has two operating modes: in Mode A, it outputs a signal value V_i, and in Mode B, it outputs a signal value W_i. Here, both V_i and W_i are non-negative integers. Takahashi first sets the operating mode of each transmitter to either A or B. Once a mode is set, it cannot be changed afterwards.

If some of the transmitters are operated simultaneously, the XOR (bitwise exclusive OR) of their output signal values is obtained as the combined signal. The set of transmitters to operate can be chosen freely, and the combined signal when the empty set is chosen is 0.

Takahashi has M target signal values T_1, T_2, \ldots, T_M. He operates them according to the following procedure:

  1. First, decide the operating mode of each transmitter to be either A or B (this decision is made only once and cannot be changed afterwards).
  2. Then, for each of the M target signal values, choose a subset of transmitters to operate so that the combined signal of the subset matches the target signal value. The subset of transmitters to operate may differ for each target signal value.

Takahashi wants to be able to realize all M target signal values. That is, after appropriately deciding the operating modes in Step 1, he wants to ensure that for every target signal value T_j (1 \leq j \leq M), there exists a subset of transmitters whose combined signal is equal to that value.

Find the number of such operating mode decisions (among the 2^N possible assignments of A or B to each transmitter) that satisfy the condition, modulo 10^9 + 7.

Constraints

  • 1 \leq N \leq 15
  • 1 \leq M \leq 100
  • 0 \leq V_i \leq 2^{60} - 1 (1 \leq i \leq N)
  • 0 \leq W_i \leq 2^{60} - 1 (1 \leq i \leq N)
  • 0 \leq T_j \leq 2^{60} - 1 (1 \leq j \leq M)
  • All input values are integers.

Input

N M
V_1 W_1
V_2 W_2
:
V_N W_N
T_1 T_2 \ldots T_M
  • The first line contains N, the number of transmitters, and M, the number of target signal values, separated by a space.
  • The next N lines, from the 2-nd to the (N + 1)-th line, give the signal values of each transmitter.
  • The (1 + i)-th line contains V_i, the signal value of transmitter i in Mode A, and W_i, the signal value of transmitter i in Mode B, separated by a space.
  • The (N + 2)-th line contains M target signal values T_1, T_2, \ldots, T_M separated by spaces.

Output

Print the number of valid operating mode decisions modulo 10^9 + 7 in a single line.

Sample Input 1

2 2
1 2
2 3
1 3

Sample Output 1

3

Sample Input 2

1 2
1 2
1 3

Sample Output 2

0

Sample Input 3

8 12
5 9
3 6
10 12
7 1
15 8
4 14
2 11
13 0
0 1 2 3 5 8 13 21 31 6 10 15

Sample Output 3

0

Sample Input 4

15 25
1 1099511627776
2 1099511627777
4 281474976710656
8 281474976710664
16 1125899906842624
32 1125899906842656
64 72057594037927936
128 72057594037928064
256 1152921504606846975
512 1152921504606846463
1024 123456789012345
2048 98765432109876
4096 555555555555555
8192 333333333333333
16384 777777777777777
0 1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 16383 32767 1099511627776 281474976710656 1125899906842624 72057594037927936 1152921504606846975 123456789012345 98765432109876 555555555555555 777777777777777

Sample Output 4

0

Sample Input 5

1 1
0 1152921504606846975
0

Sample Output 5

2