← 返回题目列表

AtCoder · typical90_ch

086. Snuke最喜欢的阵列(★5)

中文机器翻译题面 查看原题

配点: 5 点

問題文

Snuke 有以下内容 2 满足两个条件的长度。 我喜欢 N 序列 我有 A = (A_1, A_2, \ldots, A_N) 。 关于

条件1 全部 关于 i (1 \leq i \leq Q) 满足 A_{x_i} \ \mathrm{OR} \ A_{y_i} \ \mathrm{OR} \ A_{z_i} = w_i (其中 \mathrm{OR} 是按位或)
条件2 全部 关于 j (1 \leq j \leq N) 满足 0 \leq A_j < 2^{60} 满足

Snuke 最喜欢的数字序列 A 的数量 无法将数量减少到小于 1000000007 后的余数。

制約

  • 3 \leq N \leq 12
  • 1 \leq Q \leq 50
  • 1 \leq x_i < y_i < z_i \leq N (1 \leq i \leq Q)
  • 0 \leq w_i < 2^{60} (1 \leq i \leq Q)
  • 所有输入均以整数形式给出

入力

输入以以下格式从标准输入提供。

N Q
x_1 y_1 z_1 w_1
\vdots
x_Q y_Q z_Q w_Q

出力

Snuke 最喜欢的数字序列 A 的数量 无法将数量减少到小于 1000000007 后的余数。


入力例 1

4 2
1 2 3 50
2 3 4 45

出力例 1

13

例如 A = (50, 32, 0, 13) 是 Snuke 最喜欢的数字序列之一。如下所示,我们可以确认满足所有给定的条件。

  • (A_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \ A_3) = (50 \ \mathrm{OR} \ 32 \ \mathrm{OR} \ 0) = 50
  • (A_2 \ \mathrm{OR} \ A_3 \ \mathrm{OR} \ A_4) = (32 \ \mathrm{OR} \ 0 \ \mathrm{OR} \ 13) = 45
  • 数列 A 每个元素的值为 小于 0 以上 2^{60} 少于

入力例 2

8 2
2 3 6 1152886174205865983
1 2 8 1116611213275394047

出力例 2

395781543

1000000007 后的余数。