Chiaki 有 $n$ 个整数 $s_0, s_1, \dots, s_{n-1}$。她定义了一个无限序列 $S$，其生成方式如下： $S_k = s_{k \bmod n} + n \cdot \lfloor \frac{k}{n} \rfloor$，其中 $k$ 是从 0 开始的索引。

对于一个连续子序列 $S[l..r]$，令 $cnt_x$ 为 $x$ 在子序列 $S[l..r]$ 中出现的次数。 那么 $S[l..r]$ 的值定义为： $$f(l, r) = \sum_{x} x \cdot cnt_x^2$$

对于两个整数 $a$ 和 $b$ ($a \le b$)，Chiaki 想要求出以下值： $$\left( \sum_{a \le l \le r \le b} f(l, r) \right) \bmod (10^9 + 7)$$

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据： 第一行包含三个整数 $n, a, b$ ($1 \le n \le 2000, 0 \le a \le b \le 10^{18}$)。 第二行包含 $n$ 个整数 $s_0, s_1, \dots, s_{n-1}$ ($0 \le s_i \le 10^9$)。 保证所有 $n$ 的总和不超过 $2 \cdot 10^4$。

输出格式

对于每组测试数据，输出一个整数表示答案。

样例

输入 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