칠판 위의 수

n개의 정수로 이루어진 수열이 칠판에 적혀 있다. Soon Sasha가 칠판으로 와서 다음 행동을 시작한다. 서로 인접한 두 수 x와 y가 있고(x가 y보다 앞에 있음), 이 둘을 지운 뒤 그 자리에 x + 2y를 적을 수 있다. 그는 하나의 수만 남을 때까지 이 연산을 수행한다. Sasha는 큰 수를 좋아하며, 가능한 가장 큰 수를 얻게 된다.

Nikita는 Sasha보다 먼저 칠판에 가서 수 중 일부를 지우려고 한다. 그에게는 q개의 선택지가 있으며, i번째 선택지에서는 li-th번째 수보다 왼쪽에 있는 모든 수와 ri-th번째 수보다 오른쪽에 있는 모든 수를 지운다. 즉, li-th번째 수부터 ri-th번째 수까지의 모든 수가 양 끝을 포함하여 칠판에 남는다. 각 선택지에 대해 Sasha의 최종 수가 얼마나 커지는지 알고 싶어 한다. 이 수는 매우 클 수 있으므로 109 + 7로 나눈 나머지를 출력한다.

첫째 줄에 두 정수 n와 q (1 ≤ n, q ≤ 105)가 주어진다. 이는 각각 칠판에 적힌 정수의 개수와 Nikita의 선택지 개수이다.

다음 줄에 칠판 위의 수열을 나타내는 n개의 정수 a1, a2, ..., an ( - 109 ≤ ai ≤ 109)가 주어진다.

이어지는 q개의 각 줄에 Nikita의 선택지를 나타내는 두 정수 li와 ri (1 ≤ li ≤ ri ≤ n)가 주어진다.

각 선택지에 대해 Sasha의 결과를 109 + 7로 나눈 나머지를 출력한다.

두 번째 예제에서 Nikita는 아무것도 지우지 않는다. Sasha는 먼저 수 1과 2를 지우고 5를 적는다. 그다음 5와 -3을 지워 -1을 얻는다. -1을 109 + 7로 나눈 나머지는 109 + 6이다.