Problem Description

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

Input

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

Output

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

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

179
268
369
437