Uzun Gözlənilən Party

Sakurako dostları üçün riyaziyyat imtahanından sonra bir party təşkil edir. Onun cəmi $n$ dostu var. $i$-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:

burada ${\mathcal{S}}_n$ uzunluğu $n$ 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 $q$ 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ş verilənləri

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ə $n$ 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ı $q$ sətirdə iki tam ədəd $l,r(1\le l\le r\le n)$ sualı təsvir edir.

Çıxış verilənləri

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

Nümunələr

Qeyd

Birinci nümunə testində, bütün dostlar party'ye gəlir. Onların gəlişinin $6$ 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\oplus 7\oplus 1)=9$;

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

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

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

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

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

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

Qiymətləndirmə

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

2. ($56$ xal): $a_1=a_2=\cdots =a_n$;

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

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

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

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

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