Highbit and Lowbit Operations

Given a positive integer, define its \(\mathrm{highbit}(x)\) as the value of the most significant bit in its binary representation. For example, \(\mathrm{highbit}(22_{(10)}) = \mathrm{highbit}(10110_{(2)}) = 10000_{(2)} = 16_{(10)}\).

Similarly, define the \(\mathrm{lowbit}(x)\) as the value of the least significant nonzero bit in its binary representation. For example, \(\mathrm{lowbit}(22_{(10)}) = \mathrm{lowbit}(10110_{(2)}) = 10_{(2)} = 2_{(10)}\).

Two operations are defined as follows:

• Operation \(1\): transform a positive integer \(x\) to \(x+\mathrm{lowbit}(x)\).
• Operation \(2\): transform a positive integer \(x\) to \(x+\mathrm{highbit}(x)\).

You are given a sequence of operations (each operation is represented by a digit, either 1 or 2) and \(q\) queries. Each query consists of three positive integers \(l, r, x\). For a query, you need to apply the operations from index \(l\) to \(r\) (inclusive, following the left-to-right order in the sequence) on the initial number \(x\), and output the resulting number modulo \(10^9+7\).

inputFormat

The input consists of several lines:

• The first line contains a positive integer \(n\) denoting the length of the operation sequence.
• The second line contains a string of \(n\) characters (each character is either '1' or '2') representing the operation sequence.
• The third line contains a positive integer \(q\), the number of queries.
• Each of the next \(q\) lines contains three space-separated positive integers \(l\), \(r\), and \(x\).

outputFormat

For each query, output a single line containing the resulting number after performing the given operations, taken modulo \(10^9+7\).

sample

3
121
2
1 2 1
2 3 2

4
8