Period Sequence

Chiaki has $n$ integers $s_0, s_1, \dots, s_{n-1}$. She defines an infinite sequence $S$ as follows.

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

Here $k$ is a zero-based index.

For a contiguous subsequence $S[l..r]$, let $cnt_x$ be the number of occurrences of $x$ in $S[l..r]$. The value of $S[l..r]$ is

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

For two integers $a$ and $b$ ($a \le b$), find the value of

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

There are multiple test cases. The first line contains an integer $T$, the number of test cases. Each test case is as follows.

The first line contains three integers $n$, $a$, and $b$ ($1 \le n \le 2000$, $0 \le a \le b \le 10^{18}$).

The second line contains $n$ integers $s_0, s_1, \dots, s_{n-1}$ ($0 \le s_i \le 10^9$).

The sum of all $n$ does not exceed $2 \cdot 10^4$.

For each test case, print one integer: the answer.