Uzun Gözlənilən Party#11715
Daxil ol

Uzun Gözlənilən Party

3 saniyə
256 meqabayt
Çətin

Sakurako dostları üçün riyaziyyat imtahanından sonra bir party təşkil edir. Onun cəmi dostu var. -ci dostun əhval-ruhiyyəsi tam ədəd a_i ilə ifadə olunur, və Sakurako'nun əhval-ruhiyyəsi sıfırdır.

Party'nin əhval-ruhiyyəsi istənilən anda artıq gəlmiş bütün dostların əhval-ruhiyyə səviyyələrinin bitwise XOR-u kimi hesablanır. Dostlar bir-bir gəlir və eyni anda iki dost gəlmir. Gəlişin hər hansı spesifik sırası üçün, Sakurako party'nin əhval-ruhiyyəsinin cəmini hər addımda hesablaya bilər.

Məsələn, əgər Sakurako'nun üç dostu varsa və onların əhval-ruhiyyələri a_1,~a_2,~a_3 müvafiq olaraqdır və onlar party'ye [3,~1,~2] sırasına uyğun gəlirlərsə, o zaman hər addımda əhval-ruhiyyələrin cəmi a_3+(a_3\oplus a_1)+(a_3\oplus a_1\oplus a_2) olacaq.

Lakin, Sakurako dostlarının dəqiq hansı sırayla gələcəyini bilmir, ona görə də o, onların gəliş sırasının bütün mümkün permutasyonları üçün əhval-ruhiyyələrin cəmini bilmək istəyir.

Rəsmi olaraq, Sakurako hesablamaq istəyir:

\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)

burada \mathcal{S_n} uzunluğu olan bütün permutasyonların qrupudur.

Bundan əlavə, Sakurako bəzən dostlarının spesifik seqmentləri ilə maraqlanır. O, yalnız əhval-ruhiyyələri a_l, a_{l+1},\dots, a_r olan dostlar party'ye gəldikdə əhval-ruhiyyələrin cəmini bilmək istəyir. Onun belə sualı var və sizdən onlara cavab verməyinizi istəyir.

Bu cəmin çox böyük ola biləcəyini nəzərə alaraq, onu 10^9+7 modulu ilə tapın.

Giriş

Birinci sətirdə iki tam ədəd n,q ~(1\le n,q \le 2\cdot 10^5) — dostların sayı və sualların sayı.

İkinci sətirdə tam ədəd a_1,a_2,\dots,a_n ~(0\le a_i < 2^{30}) — Sakurako'nun dostlarının əhval-ruhiyyələri.

Sonrakı sətirdə iki tam ədəd l, r ~(1\le l\le r\le n) sualı təsvir edir.

Çıxış

Hər sual üçün cavabı 10^9+7 modulu ilə çıxarın.

Nümunələr

Nümunə

Loading
Loading

Nümunə 1

Loading
Loading

Qeyd

Birinci nümunə testində, bütün dostlar party'ye gəlir. Onların gəlişinin mümkün sırası var:

  1. [1, ~2, ~3]: hər addımda əhval-ruhiyyələrin cəmi 4 + (4\oplus 7) + (4\oplus7\oplus 1)=9;

  2. [1, ~3, ~2]: hər addımda əhval-ruhiyyələrin cəmi 4+(4\oplus1)+(4\oplus1\oplus7)=11;

  3. [2, ~1, ~3]: əhval-ruhiyyələrin cəmi 7 + (7\oplus 4) + (7\oplus4\oplus1)=12;

  4. [2, ~3, ~1]: əhval-ruhiyyələrin cəmi 7 + (7\oplus 1) + (7\oplus1\oplus4)=15;

  5. [3, ~1, ~2]: əhval-ruhiyyələrin cəmi 1+(1\oplus 4)+(1\oplus4\oplus7)=8;

  6. [3, ~2, ~1]: əhval-ruhiyyələrin cəmi 1+(1\oplus 7)+(1\oplus7\oplus4)=9.

Buna görə də, əhval-ruhiyyələrin ümumi cəmi 9+11+12+15+8+9=64-dir.

Bal hesablama

  1. ( xal): n\le 10, ~q=1;

  2. ( xal): a_1=a_2=\dots=a_n;

  3. ( xal): a_i\in\{0,~1\}, ~n\le 1000, ~q=1;

  4. ( xal): n\le 1000, ~q=1;

  5. ( xal): n\cdot q\le 5\cdot 10^5;

  6. ( xal): a_i\in\{0,~1\};

  7. ( xal): əlavə məhdudiyyətlər olmadan.