주기 수열

찌아키에게 정수 $n$개 $s_0, s_1, \dots, s_{n-1}$이 있다. 찌아키는 다음 방식으로 무한 수열 $S$를 정의한다.

$S_k = s_{k \bmod n} + n \cdot \left\lfloor \frac{k}{n} \right\rfloor$

여기서 $k$는 0부터 시작하는 인덱스이다.

연속 부분 수열 $S[l..r]$에 대해 $cnt_x$를 $S[l..r]$에 나타나는 $x$의 개수라고 하자. 그러면 $S[l..r]$의 값은 다음과 같다.

$f(l,r)=\sum_{x} x \cdot cnt_x^2$

두 정수 $a$, $b$ ($a \le b$)에 대해 다음 값을 구하라.

$\left(\sum_{a \le l \le r \le b} f(l,r)\right) \bmod (10^9+7)$

여러 개의 테스트 케이스가 주어진다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 세 정수 $n$, $a$, $b$ ($1 \le n \le 2000$, $0 \le a \le b \le 10^{18}$)가 주어진다.

둘째 줄에 $n$개의 정수 $s_0, s_1, \dots, s_{n-1}$ ($0 \le s_i \le 10^9$)이 주어진다.

모든 테스트 케이스의 $n$의 합은 $2 \cdot 10^4$를 넘지 않는다.

각 테스트 케이스마다 답을 정수로 한 줄에 출력한다.