시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 1024 MB64301242.857%

문제

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

리프는 코드포스 레드를 가기 위해 구사과에게 특별 훈련을 받고 있다. 구사과는 리프에게 수열 $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$로 나눈 나머지를 한 줄에 하나씩 출력한다.

제한

  • $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$

서브태스크

번호배점제한
110

$1 \le N \le 100$, $1 \le Q \le 50$

215

$1 \le N \le 1000$, $1 \le Q \le 50$

322

$1 \le N \le 3000$, $1 \le Q \le 3000$

423

$Q = 1$

520

$1 \le N \le 10^5$, $1 \le Q \le 10^5$

610

추가 제한 조건이 없다.

예제 입력 1

5 5
1 2 3 1 2
1 5
1 2
2 4
3 3
4 5

예제 출력 1

18
12
10
3
12

예제 입력 2

1 1
20
1 1

예제 출력 2

1

예제 입력 3

10 5
2 2 2 2 2 2 2 2 2 2
1 10
1 1
3 8
10 10
2 5

예제 출력 3

220
55
200
55
164

출처

Contest > BOJ User Contest > Orange Cup > Orange Cup G번

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.