시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 256 MB 0 0 0 0.000%

문제

Chiaki has $n$ integers $s_0,s_1,\dots,s_{n-1}$. She has defined an infinite sequence $S$ in the following way: $S_k = s_{k \bmod n} + n \cdot \lfloor \frac{k}{n} \rfloor$, where $k$ is a zero based index.

For a continuous subsequence $S[l..r]$, let $cnt_x$ be the number of occurrence of $x$ in the subsequence $S[l..r]$. Then the value of $S[l..r]$ is defined as follows $$f(l,r)=\sum\limits_{x}x \cdot cnt^2_x$$

For two integers $a$ and $b$ ($a \le b$), Chiaki would like to find the value of $$(\sum\limits_{a \le l \le r \le b} f(l,r)) \bmod (10^9+7)$$

입력

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

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$).

It is guaranteed that the sum of all $n$ does not exceed $2 \cdot 10^4$.

출력

For each test case, output an integer denoting the answer.

예제 입력 1

4
3 2 6
2 1 3
5 2 7
2 1 5 1 2
4 4 8
2 1 5 17
3 5 9
2 5 2

예제 출력 1

179
268
369
437