JATC любит Бань-ми (вьетнамское блюдо). Его привяз...

JATC любит Бань-ми (вьетнамское блюдо). Его привязанность к Бань-ми настолько велика, что он ест Бань-ми каждый день на завтрак. Сегодня утром, как обычно, он купил Бань-ми, но собирается насладиться им необычным образом.

Сначала, он разбивает Бань-ми на n
кусочков, выкладывает их в ряд и нумерует от 1
до n
. Для каждого кусочка i
он определяет его вкусность как xi∈{0,1}
. JATC собирается съесть все кусочки один за другим. Каждый раз он выбирает произвольный из оставшихся кусочков и съедает его. Пусть этот кусочек был под номером i
, тогда его удовольствие от Бань-ми увеличивается на xi
, вкусность каждого из оставшихся кусочков также увеличивается на xi
. Изначально удовольствие JATC равно 0
.

Например, пусть есть 3
кусочка с вкусностями [0,1,0]
. Если JATC съест второй кусочек, то его удовольствие станет равно 1
, а вкусность оставшихся кусочков будет равна [1,,1]
. Затем, если он съест первый кусочек, то его удовольствие станет равна 2
, а вкусность оставшихся кусочков станет [,_,2]
. После того как JATC съест последний кусочек, его удовольствие станет равно 4
.

Однако JATC не хочет съесть сразу все кусочки, оставив часть на будущее. Он дал вам q
запросов, каждый из которых задаётся двумя целыми числам li
и ri
. Для каждого запроса выясните какое наибольшее удовольствие он может получить, если съест все кусочки в отрезке [li,ri]
в каком-то порядке.

Все запросы независимы друг от друга. Так как ответ на запрос может быть очень большим, выведите его по модулю 109+7
.

Входные данные
Первая строка содержит два целых числа n
и q
(1≤n,q≤100000
).

Вторая строка содержит строку из n
символов, каждый из которых равен или '0' или '1'. Символ под номером i
определяет вкусность i
-го кусочка.

Каждая из следующих q
строк содержит по два целых числа li
или ri
(1≤li≤ri≤n
) — отрезок соответствующего запроса.

Выходные данные
Выведите q
строчек, где i
-я из них содержит одно целое число — ответ на i
-й запрос по модулю 109+7
.

Примеры
Входные данныеСкопировать
4 2
1011
1 4
3 4
Выходные данныеСкопировать
14
3
Входные данныеСкопировать
3 2
111
1 2
3 3
Выходные данныеСкопировать
3
1
Примечание
В первом примере:

В запросе 1
, одним из оптимальных порядков поедания является следующий: 1
, 4
, 3
, 2
.
В запросе 2
: и порядок 3
, 4
, и порядок 4
, 3
приводят к одному и тому же ответу.
Во втором примере любой порядок поедания кусочков приведёт к одному и тому же ответу.

#include <bits/stdc++.h>
#define int long long
using namespace std;

using i128 = __int128;
using ld = long double;
const int INF = 1e15;
const int N = 1e6 + 7;
const int MOD = 1e9 + 7;

void solve() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
vector< int > pref(n + 1);
for (int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] + (s[i - 1] - '0');
}

while (q--) {
int l, r;
cin >> l >> r;
int x = r - l + 1;
int y = x - (pref[r] - pref[l - 1]);
cout << ((x * (x + 1) * (x + 2) / 6) - (y * (y + 1) / 2)) % MOD << "\n";
}
}

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int tests = 1;
//cin >> tests;
while (tests--) {
solve();
}

return 0;
}
в формуле есть небольшая ошибка исправь ошибку не меняя рнешения и решая формулой + минимально изменить элементы в коде