시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 | 256 MB | 7 | 4 | 3 | 50.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.
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