Array Distances

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

You have been given an array of N unique integers (with starting index 1) and Q queries to perform. For each query, you are given an index j. For each integer in the array, you must calculate the product of the integer and the distance between their index and the given index j. That is, if the integer has index i you must calculate x_i\times(|i-j|). Output, for each query, the sum of the calculations for all integers in the array, modulo 10^9+7.

Input Specification

The first line will contain two integers, N and Q (1 \leq N, Q \leq 10^5), separated by a space. The second line will contain N space-separated unique integers, x_1, x_2, \ldots, x_N (0 \leq x_i \leq 10^4). The next Q lines will contain one integer, an index y (1 \leq y \leq N).

Output Specification

Output, on separate lines, the answer to each query, modulo 10^9+7.

Subtasks

Subtask 1 [20%]

N \leq 10^3

Q \leq 10^3

Subtask 2 [80%]

No additional constraints.

Sample Input 1

9 5
10 6 4 5 6 4 11 9 3 
8
3
7
5
2

Sample Output 1

186
162
152
136
188

Sample Input 2

9 3
4 5 4 11 11 10 7 9 6 
4
2
8

Sample Output 2

144
234
188

Explanation for Sample Input 1

For the first query, j = 8. The calculations then become: 10\times7+6\times6+4\times5+5\times4+6\times3+4\times2+11\times1+9\times0+3\times1 = 186


Comments

There are no comments at the moment.