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

Сакурако організовує вечірку для своїх друзів після їхнього тесту з математики. У нього всього $n$ друзів. Настрій $i$-го друга представлений цілим числом $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)$.

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

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

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

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

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

Вхідні дані

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

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

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

Вихідні дані

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

Приклади

Примітка

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

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

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

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

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

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

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

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

Оцінювання

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

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

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

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

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

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

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