Задача . The Best Subsequence

У Фермера Джона есть двоичная строка длиной \(N\) \((1 \leq N \leq 10^9)\), изначально из одних нулей.

Сначала он выполнит \(M\) (\(1 \leq M \leq 2 \cdot 10^5\)) изменений строки по порядку. Каждое изменение переворачивает каждый символ от \(l\) до \(r\). То есть \(0\) изменяется на \(1\) и наоборот.

Затем он задаёт Вам \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) вопросов. Для каждого вопроса Вы должны ввести лексикографически наибольшую подпоследовательность длины \(k\) состоящую из символов подстроки от \(l\) до \(r\). Если Ваш ответ - двоичная строка \(s_1s_2 \dots s_k\), выведите \(\sum_{i=0}^{k-1} 2^i \cdot s_{k-i}\) (то есть строка интерпретируется как двоичное число) по модулю \(10^9+7\).

Подпоследовательность это строка, которая может быть получена из другой строки удалением (или не удалением) символов без изменения порядка оставшихся символов.

Напомним, что строка \(A\) лексикографически больше чем строка \(B\) такой же длины если и только если в первой позиции \(i\), если она существует, \(A_i \neq B_i\), выполняется \(A_i > B_i\).

ПР�МЕР ВВОДА:

5 3 9
1 5
2 4
3 3
1 5 5
1 5 4
1 5 3
1 5 2
1 5 1
2 5 4
2 5 3
2 5 2
2 5 1

ПР�МЕР ВЫВОДА:

21
13
7
3
1
5
5
3
1

После выполнения \(M\) операций, строка такова: \(10101\).

Для первого запроса - длины \(5\) ответ вся строка \(10101\), которая интерпретируется как \(1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 21\).

Для второго запроса, существует \(5\) уникальных подпоследовательностей длины \(4\): \(0101\), \(1101\), \(1001\), \(1011\), \(1010\). Лексикографически наибольшая из них \(1101\), которая интерпретируется как \(1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1\cdot 2^0 = 13\).

Для третьей строки лексикографически наибольшая последовательность \(111\), которая интерпретируется как \(7\).

ПР�МЕР ВВОДА:

9 1 1
7 9
1 8 8

ПР�МЕР ВЫВОДА:

3

ПР�МЕР ВВОДА:

30 1 1
1 30
1 30 30

ПР�МЕР ВЫВОДА:

73741816

Не забудьте выводить ответ по модулю \(10^9+7\).

Автор: Chongtian Ma

21
13
7
3
1
5
5
3
1