오렌지 리프의 특별 훈련

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

리프는 코드포스 레드를 가기 위해 구사과에게 특별 훈련을 받고 있다. 구사과는 리프에게 수열 $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$ 개의 줄에는 구사과의 $Q$ 개의 질문을 나타내는 두 정수 $l\_i$ $r\_i$ 가 주어진다.

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