Pipes selection

Mario works at a factory. There are $n$ pipes in a row. Let us label the pipes $1, 2, 3,\ldots, n$ from left to right. The factory will deliver $a_i$ units of water per second through pipe $i$ for $i$ from $1$ to $n$. His job is to open some consecutive pipes to make them output exactly $j$ units of water per second, but he doesn't know how to do it. Help Mario to find which segment of pipes to open.

You are given $a_1, a_2, a_3, \ldots,a_n$. Let $s=\sum\limits_{i=1}^{n}a_i$. Your task is to find $(l_j, r_j)$ for all $j$ from $1$ to $s$ such that $j=a_{l_j}+a_{l_{j}+1}+\ldots +a_{r_j}$. Because of his boss' command, if there are $k$ possible $(l, r)$ for $j$, then $(l_j, r_j)$ is the $\lfloor \dfrac{k+1}{2} \rfloor$-th smallest one of all possible $(l, r)$. If there are no possible $(l,r)$ for $j$, then $(l_j, r_j)=(0, 0)$.

We say $(x, y)$ is smaller than $(z, w)$ if $x<z$ or ( $x=z$ and $y<w$ ).

For example, $n=4$ and ($a_1$, $a_2$, $a_3$, $a_4$)$=$($2$, $1$, $1$, $2$), then we can find ($(l_1,r_1)$, $(l_2,r_2)$, $(l_3,r_3)$, $(l_4,r_4)$, $(l_5,r_5)$, $(l_6,r_6)$)$=$($(2,2)$, $(2,3)$, $(1,2)$, $(1,3)$, $(0,0)$, $(1,4)$).

There are $2$ possible $(l,r)$ for $1$ which are $(2,2),(3,3)$ and $(l_1,r_1)$ is the $1$-th smallest, so $(l_1,r_1)=(2,2)$.
There are $3$ possible $(l,r)$ for $2$ which are $(1,1),(2,3),(4,4)$ and $(l_2,r_2)$ is the $2$-th smallest, so $(l_2,r_2)=(2,3)$.
There are $2$ possible $(l,r)$ for $3$ which are $(1,2),(3,4)$ and $(l_3,r_3)$ is the $1$-th smallest, so $(l_3,r_3)=(1,2)$.
There are $2$ possible $(l,r)$ for $4$ which are $(1,3),(2,4)$ and $(l_4,r_4)$ is the $1$-th smallest, so $(l_4,r_4)=(1,3)$.
There are no possible $(l,r)$ for $5$, so $(l_5,r_5)=(0,0)$.
There is $1$ possible $(l,r)$ for $6$ which is $(1,4)$ and $(l_6,r_6)$ is the $1$-th smallest, so $(l_6,r_6)=(1,4)$.

The first line contains an integer $t$ indicating the total number of test cases. The following lines describe a test case.

The first line of each case contains one integer $n$, the number of pipes.
The second line contains $n$ integers, representing $a_1, a_2, a_3, \ldots, a_n$.

$1 \le t \le 20$
$0 \le \text{ min}(a_i)$
$1 \le \text{ max}(n,s) \le 30000$
There are at most 5 test cases with $\text{ max}(n,s)>10000$.

For each test case, output on a single line two integers $\sum\limits_{j=1}^{s}((233)^j\times l_j)$ modulo $10^9+7$ and $\sum\limits_{j=1}^{s}((233)^j\times r_j)$ modulo $10^9+7$.

3
4
2 1 1 2
4
0 1 0 0
6
2 3 2 3 2 1

685473415 769026629
233 932
811854151 883301517