Maximum XOR of Two Disjoint Subsequences

You are given a binary string s of length \(n\) (a string consisting of characters '0' and '1'). You are also given \(q\) queries. In each query, you are given three integers \(l\), \(r\), and \(k\). Consider the substring \(s[l,r]\) (1-indexed). From this substring, you must choose two disjoint subsequences of length \(k\) each. A subsequence is obtained by choosing \(k\) indices \(p_1, p_2, \dots, p_k\) in increasing order (i.e. \(l \le p_1 < p_2 < \cdots < p_k \le r\)) for the first subsequence, and similarly indices \(q_1, q_2, \dots, q_k\) for the second subsequence with the only restriction that for any \(1 \le i,j \le k\) we have \(p_i \neq q_j\) (i.e. the two subsequences use distinct positions).

Each subsequence represents a \(k\)-digit binary number (the bits taken in the chosen order). Let the decimal value of such a binary number be the usual interpretation in base \(2\) (for instance, the binary string \(101\) represents \(5\)). For a query, your task is to maximize the value of the bitwise XOR of the two chosen numbers. Since the answer can be very large, output it modulo \(10^9+7\).

Observation: The maximum possible XOR is obtained when the two numbers are bitwise complements (i.e. one is \(0\ldots0\) and the other is \(1\ldots1\)), which gives \(2^k-1\). However, it may not always be possible to achieve this ideal if one of the bits ('0' or '1') is scarce in \(s[l,r]\). Let \(cnt_0\) be the number of '0's in \(s[l,r]\) and \(cnt_1\) be the number of '1's. Note that since we must choose a total of \(2k\) distinct indices from \(s[l,r]\), it is guaranteed that \(r-l+1\ge2k\).

Optimal Strategy:

• If both \(cnt_0\ge k\) and \(cnt_1\ge k\), then one can choose one subsequence to be all zeros and the other all ones, achieving an XOR of \(2^k-1\).
• If one of \(cnt_0\) or \(cnt_1\) is less than \(k\), let \(t=\min(cnt_0, cnt_1)\). Then the best you can do is to differentiate in the most significant \(t\) bit positions. In that case, the maximum achievable XOR is \[ 2^k-2^{k-t} \] This is because you can force the first \(t\) bits (most significant bits) to be different and the remaining \(k-t\) bits will be the same.

Compute the answer for each query modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(q\) -- the length of the binary string and the number of queries, respectively. The second line contains the binary string \(s\) of length \(n\). Each of the next \(q\) lines contains three integers \(l\), \(r\), and \(k\). It is guaranteed that \(r-l+1 \ge 2k\).

Example:

10 3
0101010111
1 10 2
1 10 3
2 5 1

outputFormat

For each query, output a single integer -- the maximum XOR value (modulo \(10^9+7\)) achievable by selecting two disjoint subsequences of length \(k\) from \(s[l,r]\).

Example Output:

3
7
1

sample

10 3
0101010111
1 10 2
1 10 3
2 5 1

3
7
1