配点: 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 后的余数。