問題文

すぬけ君は、以下の 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} を満たす

すぬけ君が好きな数列 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)
• 入力はすべて整数で与えられる

入力例 1

4 2
1 2 3 50
2 3 4 45

出力例 1

13

例えば A = (50, 32, 0, 13) は、すぬけ君が好きな数列の一つです。以下の通り、与えられたすべての条件を満たすことが確認できます。

• (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 で割った余りを出力してください。