Chiaki has n
integers s0,s1,…,sn−1
. She has defined an infinite sequence S
in the following way: Sk=skmodn+n⋅⌊kn⌋
, where k
is a zero based index.
For a continuous subsequence S[l..r]
, let cntx
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)=∑xx⋅cnt2x
For two integers a
and b
(a≤b
), Chiaki would like to find the value of
(∑a≤l≤r≤bf(l,r))mod(109+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≤n≤2000,0≤a≤b≤1018).
The second line contains n integers s0,s1,…,sn−1 (0≤si≤109).
It is guaranteed that the sum of all n does not exceed 20000.