수열과 쿼리 2017  시간제한 : 5초

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