Divan and bitwise operations (Codeforces 1614C)
Tags: Math, combinatorics

Once Divan analyzed a sequence $$$a_1, a_2, \ldots, a_n$$$ consisting of $$$n$$$ non-negative integers as follows. He considered each non-empty subsequence of the sequence $$$a$$$, computed the bitwise XOR of its elements and added up all the XORs, obtaining the coziness of the sequence $$$a$$$.A sequence $$$c$$$ is a subsequence of a sequence $$$d$$$ if $$$c$$$ can be obtained from $$$d$$$ by deletion of several (possibly, zero or all) elements. For example, $$$[1, \, 2, \, 3, \, 4]$$$, $$$[2, \, 4]$$$, and $$$[2]$$$ are subsequences of $$$[1, \, 2, \, 3, \, 4]$$$, but $$$[4, \, 3]$$$ and $$$[0]$$$ are not.Divan was very proud of his analysis, but now he lost the sequence $$$a$$$, and also the coziness value! However, Divan remembers the value of bitwise OR on $$$m$$$ contiguous subsegments of the sequence $$$a$$$. It turns out that each element of the original sequence is contained in at least one of these $$$m$$$ segments.Divan asks you to help find the coziness of the sequence $$$a$$$ using the information he remembers. If several coziness values are possible, print any.As the result can be very large, print the value modulo $$$10^9 + 7$$$.

Input: The first line contains one integer number $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.The first line of each test case contains two integer numbers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of the sequence and the number of contiguous segments whose bitwise OR values Divan remembers, respectively.The following $$$m$$$ lines describe the segments, one per line.Each segment is described with three integers $$$l$$$, $$$r$$$, and $$$x$$$ ($$$1 \le l \le r \le n$$$, $$$0 \le x \le 2^{30} - 1$$$) — the first and last elements of the segment and the bitwise OR of $$$a_l, a_{l + 1}, \ldots, a_r$$$, respectively.It is guaranteed that each element of the sequence is contained in at least one of the segments. It is guaranteed that there exists a sequence that satisfies all constraints.It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$. 

Output: For each test case print the coziness any suitable sequence $$$a$$$ modulo $$$10^9 + 7$$$.

Note: In first example, one of the sequences that fits the constraints is $$$[0, 2]$$$. Consider all its non-empty subsequences:  $$$[0]$$$: the bitwise XOR of this subsequence is $$$0$$$;  $$$[2]$$$: the bitwise XOR of this subsequence is $$$2$$$;  $$$[0, 2]$$$: the bitwise XOR of this subsequence is $$$2$$$. The sum of all results is $$$4$$$, so it is the answer.In second example, one of the sequences that fits the constraints is $$$[0, \, 5, \, 5]$$$.In third example, one of the sequences that fits the constraints is $$$[5, \, 6, \, 7, \, 0, \, 2]$$$.

Sample Inputs:
3
2 1
1 2 2
3 2
1 3 5
2 3 5
5 4
1 2 7
3 3 7
4 4 0
4 5 2

Sample Outputs:
4
20
112

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import math
import bisect
t = int(input())
mod = 10 ** 9 + 7
for a0 in range(t):
    (n, m) = [int(i) for i in input().split()]
    z = 0
    for i in range(m):
        (l, r, x) = [int(i) for i in input().split()]
        z = z | x
    print(z * 2 ** (n - 1) % mod)

Solution (Python):
MOD = 1000000007

def solve():
    (n, m) = [int(x) for x in input().split()]
    total_or = 0
    for _ in range(m):
        (l, r, x) = [int(x) for x in input().split()]
        total_or |= x
    ans = 2 ** (n - 1) * total_or
    print(ans % MOD)
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
t = int(input())
import sys
input = sys.stdin.readline
MOD = int(1000000000.0 + 7)

def power(x, y, p):
    res = 1
    x = x % p
    if x == 0:
        return 0
    while y > 0:
        if y & 1 == 1:
            res = res * x % p
        y = y >> 1
        x = x * x % p
    return res
for _ in range(t):
    (n, m) = map(int, input().split())
    a = 0
    for i in range(m):
        (l, r, x) = map(int, input().split())
        a |= x
    a = a % MOD
    val = power(2, n - 1, MOD)
    print(val * a % MOD)