Fête tant attendue#11715
Sakurako organise une fête pour ses amis après leur test de mathématiques. Il a au total amis. L'humeur du -ème ami est représentée par un entier a_i, et l'humeur de Sakurako est zéro.
L'humeur de la fête à tout moment est calculée comme le XOR bit à bit des niveaux d'humeur de tous les amis qui sont déjà arrivés. Les amis arrivent à la fête un par un, et aucun deux amis n'arrivent en même temps. Pour un ordre d'arrivée spécifique, Sakurako peut calculer la somme totale de l'humeur de la fête à chaque étape.
Par exemple, si Sakurako a trois amis avec des humeurs a_1,~a_2,~a_3 respectivement et qu'ils viennent à la fête dans l'ordre [3,~1,~2], alors la somme des humeurs à chaque étape est a_3+(a_3\oplus a_1)+(a_3\oplus a_1\oplus a_2).
Cependant, comme Sakurako ne connaît pas l'ordre exact dans lequel ses amis arriveront, il veut connaître la somme totale des humeurs pour toutes les permutations possibles de leur ordre d'arrivée.
Formellement, Sakurako veut calculer :
où \mathcal{S_n} est un groupe de toutes les permutations de longueur .
De plus, Sakurako est parfois curieux au sujet de segments spécifiques de ses amis. Il veut connaître la somme totale des humeurs si seulement les amis avec des humeurs a_l, a_{l+1},\dots, a_r arrivent à la fête. Il a telles questions et vous demande d'y répondre.
Comme cette somme peut être trop grande, trouvez-la modulo 10^9+7.
La première ligne contient deux entiers n,q ~(1\le n,q \le 2\cdot 10^5) — le nombre d'amis et le nombre de questions.
La deuxième ligne contient entiers a_1,a_2,\dots,a_n ~(0\le a_i < 2^{30}) — humeurs des amis de Sakurako.
Chacune des lignes suivantes contient deux entiers l, r ~(1\le l\le r\le n) décrivant la question.
Pour chaque question, sortez la réponse modulo 10^9+7.
Exemple
Exemple 1
Dans le premier exemple de test, tous les amis viennent à la fête. Il y a ordres possibles de leur arrivée :
[1, ~2, ~3]: la somme des humeurs à chaque étape est 4 + (4\oplus 7) + (4\oplus7\oplus 1)=9;
[1, ~3, ~2]: la somme des humeurs à chaque étape est 4+(4\oplus1)+(4\oplus1\oplus7)=11;
[2, ~1, ~3]: la somme des humeurs est 7 + (7\oplus 4) + (7\oplus4\oplus1)=12;
[2, ~3, ~1]: la somme des humeurs est 7 + (7\oplus 1) + (7\oplus1\oplus4)=15;
[3, ~1, ~2]: la somme des humeurs est 1+(1\oplus 4)+(1\oplus4\oplus7)=8;
[3, ~2, ~1]: la somme des humeurs est 1+(1\oplus 7)+(1\oplus7\oplus4)=9.
Ainsi, la somme totale des humeurs est 9+11+12+15+8+9=64.
( points) : n\le 10, ~q=1 ;
( points) : a_1=a_2=\dots=a_n ;
( points) : a_i\in\{0,~1\}, ~n\le 1000, ~q=1 ;
( points) : n\le 1000, ~q=1 ;
( points) : n\cdot q\le 5\cdot 10^5 ;
( points) : a_i\in\{0,~1\} ;
( points) : sans restrictions supplémentaires.