Informatica Online Judge

  수열과 쿼리 [2124 / 084C]

Time Limit(Test case) : 5000(ms)
Number of users who solved : 6   Total Tried : 6


The Champion of this Problem (C++) : gs16106 - 56ms / 1325byte
My Best Submission (C++) : N/A

[koistudy.net (34th 김현수)]

Background

현수는 수열과 쿼리 문제 시리즈의 추종자이다. 현수가 만든 새로운 쿼리 문제를 풀어보자.

길이가 N인 수열 A1, A2, ..., AN이 주어진다.

i j k: i ≤ p ≤ j일 때 k = Ap 인 p의 갯수 X라 하자.

(X*k)C(k)를 2017로 나눈 나머지를 출력하자.

위 기호 C는 Combination을 의미한다.

Input

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000,000,000)

셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

넷째 줄부터 M개의 줄에는 쿼리 i, j, k가 한 줄에 하나씩 주어진다.

(1 ≤ i ≤ j ≤ n) (1≤k≤1,000,000,000)

Output

각각의 쿼리마다 정답을 2017로 나눈 나머지를 한 줄에 하나씩 출력하시오.

IO Example

입력
5
2 2 200 2 200
4
1 5 2
2 4 2
3 5 200
1 2 1

출력
15
6
1713
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]