This question is from yesterday’s interviewbit academy entrance test. So the link is unavailable now.

Given an array A of size n.

1 \leq n \leq 10^5

1 \leq A[i] \leq 10^3

find the (\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} A[i] \% A[j]) \% (1e9 + 7)

In other words calculate sum of A[i] \% A[j] for all valid values of i,j and then sum \% (1e9 + 7) .

**For Example**

Input 1 :

A = [1,2,3]

Output 1 :

5

Explanation 1 :

(1 \% 1) + (1 \% 2) + (1 \% 3)

+ (2 \% 1) + (2 \% 2) + (2 \% 3)

+ (3 \% 1) + (3 \%2) + (3 \% 3)

= 5

Input 2 :

A=[17, 100, 11]

Output 2 :

61

I have applied brute force method. But there might be another way. Kindly give approach.