오렌지 리프의 특별 훈련

이 문제는 인터랙티브 문제가 아닙니다.

리프는 코드포스 레드에 가기 위해 구사과에게 특별 훈련을 받고 있다. 구사과는 리프에게 수열 $A$를 주고, 구사과가 생각한 수열 위의 구간 $I=[a, b]$ 안에 있는 수들의 값을 맞춰 보라고 했다.

리프는 구사과에게 다음과 같은 질문을 할 수 있다.

• $[i, j]$ 구간과 $[a, b]$ 구간의 최장 공통 접두사의 길이는 얼마인가? (예를 들어 $A=[1, 2, 1, 2, 3]$인 경우 $[1, 4]$ 구간과 $[3, 5]$ 구간의 최장 공통 접두사의 길이는 2이다.)

원래는 리프가 구사과에게 적은 횟수의 질문을 해서 $[a, b]$ 안의 수들의 값을 맞춰야 했다. 하지만 구사과가 깜박하고 질문 횟수 제한을 거는 것을 잊어버렸다. 리프는 모든 구간에 대해 위와 같은 질문을 하고, 구사과가 낸 문제를 쉽게 풀어 냈다.

이렇게 된 이상, 구사과는 리프에게 아래와 같은 문제를 $Q$개 내고 빠르게 풀라고 했다. 리프를 도와 구사과가 낸 문제를 빠르게 푸는 프로그램을 작성해 보자.

• 구사과가 생각한 구간이 $[l_i, r_i]$일 때, 리프가 모든 구간에 대해 위와 같은 질문을 한다면 구사과 대답의 총합은 얼마인가?

첫 줄에는 구사과가 만든 수열의 길이 $N$과 구사과의 질문 횟수 $Q$가 주어진다.

둘째 줄에는 수열 $A$의 각 원소 $A_1, A_2, \cdots, A_N$이 주어진다.

셋째 줄부터 $Q+2$번째 줄까지 $Q$개의 줄에 구사과의 질문을 나타내는 두 정수 $l_i$, $r_i$가 주어진다.

$Q$개의 질문에 대한 답을 $MOD$로 나눈 나머지를 한 줄에 하나씩 출력한다.

• $1 \le N \le 3 \times 10^5$
• $1 \le Q \le 10^6$
• $1 \le l \le r \le N$
• $1 \le A_i \le 10^9$
• $MOD = 10^9+7$