Довгоочікувана вечірка#11715
Увійти

Довгоочікувана вечірка

3 секунди
256 мегабайтів
Складна

Сакурако організовує вечірку для своїх друзів після їхнього тесту з математики. У нього всього друзів. Настрій -го друга представлений цілим числом a_i, а настрій Сакурако дорівнює нулю.

Настрій вечірки в будь-який момент розраховується як побітове XOR рівнів настрою всіх друзів, які вже прийшли. Друзі приходять на вечірку по одному, і жоден з друзів не приходить в один і той же час. Для будь-якого конкретного порядку прибуття Сакурако може розрахувати загальну суму настрою вечірки на кожному етапі.

Наприклад, якщо у Сакурако є троє друзів з настроями a_1,~a_2,~a_3 відповідно, і вони приходять на вечірку в порядку [3,~1,~2], тоді сума настроїв на кожному етапі дорівнює a_3+(a_3\oplus a_1)+(a_3\oplus a_1\oplus a_2).

Однак, оскільки Сакурако не знає точного порядку, в якому його друзі прийдуть, він хоче дізнатися загальну суму настроїв для всіх можливих перестановок їхнього порядку прибуття.

Формально, Сакурако хоче знайти:

\displaystyle \sum_{p\in\mathcal{S_n}}\sum_{k=1}^{n}\bigg(a_{p_1}\oplus a_{p_2}\oplus\dots\oplus a_{p_k}\bigg)

де \mathcal{S_n} — це група всіх перестановок довжини .

Крім того, Сакурако іноді цікавиться конкретними відрізками своїх друзів. Він хоче дізнатися загальну суму настроїв, якщо на вечірку прийдуть лише друзі з настроями a_l, a_{l+1},\dots, a_r. У нього є таких запитань, і він просить вас на них відповісти.

Оскільки ця сума може бути занадто великою, знайдіть її за модулем 10^9+7.

Вхідні дані

Перший рядок містить два цілі числа n,q ~(1\le n,q \le 2\cdot 10^5) — кількість друзів та кількість запитань.

Другий рядок містить цілих чисел a_1,a_2,\dots,a_n ~(0\le a_i < 2^{30}) — настрої друзів Сакурако.

Кожен з наступних рядків містить два цілі числа l, r ~(1\le l\le r\le n), що описують запит.

Вихідні дані

Для кожного запитання виведіть відповідь за модулем 10^9+7.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

У першому тестовому прикладі всі друзі приходять на вечірку. Є можливих порядків їх прибуття:

  1. [1, ~2, ~3]: сума настроїв на кожному етапі дорівнює 4 + (4\oplus 7) + (4\oplus7\oplus 1)=9;

  2. [1, ~3, ~2]: сума настроїв на кожному етапі дорівнює 4+(4\oplus1)+(4\oplus1\oplus7)=11;

  3. [2, ~1, ~3]: сума настроїв дорівнює 7 + (7\oplus 4) + (7\oplus4\oplus1)=12;

  4. [2, ~3, ~1]: сума настроїв дорівнює 7 + (7\oplus 1) + (7\oplus1\oplus4)=15;

  5. [3, ~1, ~2]: сума настроїв дорівнює 1+(1\oplus 4)+(1\oplus4\oplus7)=8;

  6. [3, ~2, ~1]: сума настроїв дорівнює 1+(1\oplus 7)+(1\oplus7\oplus4)=9.

Отже, загальна сума настроїв дорівнює 9+11+12+15+8+9=64.

Оцінювання

  1. ( балів): n\le 10, ~q=1;

  2. ( балів): a_1=a_2=\dots=a_n;

  3. ( балів): a_i\in\{0,~1\}, ~n\le 1000, ~q=1;

  4. ( балів): n\le 1000, ~q=1;

  5. ( бали): n\cdot q\le 5\cdot 10^5;

  6. ( бали): a_i\in\{0,~1\};

  7. ( бали): без додаткових обмежень.