Clacking Balls
Contest: Codeforces Global Round 25
Difficulty rating: 3100
Tags: combinatorics, math, probabilities

There are $$$m$$$ baskets placed along a circle, numbered from $$$1$$$ to $$$m$$$ in clockwise order (basket $$$m$$$ is next to basket $$$1$$$). Furthermore, there are $$$n$$$ balls, where ball $$$i$$$ is initially placed in basket $$$a_i$$$, and no basket contains more than one ball.

Alice is allowed to perform the following operation, which always takes exactly one second whether you move/throw a ball or not:

- Alice chooses an integer $$$i$$$ between $$$1$$$ and $$$n$$$ uniformly at random.
- If ball $$$i$$$ was thrown away before, do nothing.
- Otherwise, ball $$$i$$$ is moved from the basket currently containing it to the next basket (in clockwise order). If the target basket currently contains another ball $$$j$$$, throw ball $$$j$$$ away.

She repeats this operation until there is exactly one ball left. Calculate the expected time needed (in seconds) for Alice to end the process.

It can be proven that the answer can be represented as a rational number $$$\frac{p}{q}$$$ with coprime $$$p$$$ and $$$q$$$. You need to output $$$p \cdot q^{-1} \bmod 10^9 + 7$$$. It can be proven that $$$10^9 + 7 \nmid q$$$.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5, n \le m \le 10^9$$$) — the number of balls and the number of baskets.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$, $$$a_i$$$'s are pairwise distinct) — the initial position of each ball.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print one integer: the expected amount of time (in seconds) Alice needs to end the process, modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Alice could have proceeded as follows (we define $$$a_i = -1$$$ if ball $$$i$$$ has been thrown out):

- Initially, $$$a = [5, 1, 4]$$$.
- Alice chooses $$$i = 2$$$ with probability $$$\frac{1}{3}$$$, and ball $$$2$$$ is moved to basket $$$2$$$. After this, $$$a = [5, 2, 4]$$$.
- Alice chooses $$$i = 2$$$ with probability $$$\frac{1}{3}$$$, and ball $$$2$$$ is moved to basket $$$3$$$. After this, $$$a = [5, 3, 4]$$$.
- Alice chooses $$$i = 2$$$ with probability $$$\frac{1}{3}$$$, and ball $$$2$$$ is moved to basket $$$4$$$. As basket $$$4$$$ previously contains ball $$$3$$$, this ball is thrown out. After this, $$$a = [5, 4, -1]$$$.
- Alice chooses $$$i = 3$$$ with probability $$$\frac{1}{3}$$$. Ball $$$3$$$ has already been thrown out, so nothing happens. After this, $$$a = [5, 4, -1]$$$.
- Alice chooses $$$i = 2$$$ with probability $$$\frac{1}{3}$$$, and ball $$$2$$$ is moved to basket $$$5$$$, which throws out ball $$$1$$$. After this, $$$a = [-1, 5, -1]$$$, and the process ends.

The answer for the second test case is $$$14$$$ (note that these two balls are next to each other).

The answer for the third test case is $$$35$$$.

The answer for the fourth test case is $$$\frac{220}{3}$$$.

In the fifth test case, as there is only one ball initially, the answer is $$$0$$$.

Example input:
5
3 10
5 1 4
2 15
15 1
6 6
1 2 3 4 5 6
6 9
6 5 4 3 2 1
1 100
69

Example output:
600000042
14
35
333333409
0

Editorial:
Note: there are other (more elegant in our opinion) solutions from some of our testers, which you may or may not find under the comment section. We will present here the original solution here.
Consider a state with $$$k \leq n$$$ balls remaining. Let's represent the state as a sequence $$$S = (d_1, d_2, \cdots, d_k)$$$ where $$$d_i$$$ is the distance between ball $$$i$$$ and ball $$$(i \bmod{k}) + 1$$$. Note that $$$\sum_{i=1}^{k} d_i = m$$$. Then, after a second, one of the following happens:
• $$$d_i$$$ is increased by $$$1$$$ and $$$d_{(i \bmod{k}) + 1}$$$ is decreased by $$$1$$$ with probability $$$\frac{1}{n}$$$ for each $$$1 \leq i \leq k$$$ (if $$$d_{(i \bmod{k}) + 1} = 0$$$, we erase it from the sequence). We denote the new sequence as $$$S + \{i\}$$$.
• Nothing changes with probability $$$1 - \frac{k}{n}$$$.
The terminal state is $$$(m)$$$. Therefore, let $$$f(S)$$$ be the expected number of seconds to reach the terminal state from state $$$S = (d_1, d_2, \cdots, d_k)$$$, then:
• $$$f((m)) = 0$$$ (*)
• $$$f(S) = 1 + \frac{1}{n} \sum_{i=1}^{k} f(S + \{i\}) + (1 - \frac{k}{n}) f(S)$$$ $$$\Rightarrow$$$ $$$k f(S) = n + \sum_{i=1}^{k} f(S + \{i\})$$$ (**)
Let $$$h(S, i) = f(S) - f(S + \{i\})$$$, condition (**) becomes $$$\sum_{i=1}^{k} h(S, i) = n$$$.
To proceed, we will apply the idea from this comment. If we choose $$$f(S) = c + \sum_{i=1}^{k} \sum_{x=0}^{d_i} g(x)$$$ for some constant $$$c$$$ and function $$$g: \mathbb{Z_{\geq 0}} \rightarrow \mathbb{R}$$$, then:
$$$n = \sum_{i=1}^{k} h(S, i)$$$
$$$= \sum_{i=1}^{k} g(d_{(i \bmod{k}) + 1}) - g(d_i + 1)$$$
$$$= \sum_{i=1}^{k} g(d_i) - g(d_i + 1)$$$
Additionally, since we want $$$h(S, i) = g(d_{(i \bmod{k}) + 1}) - g(d_i + 1)$$$ to hold even when $$$d_{(i \bmod{k}) + 1} = 0$$$, we need to choose $$$g$$$ such that $$$g(0) = 0$$$.
Let's choose $$$g$$$ such that $$$g(0) = 0$$$ and $$$g(x + 1) - g(x) = -\frac{n}{m}x$$$ for all $$$x \geq 0$$$. Then $$$\sum_{i=1}^{k} g(d_i) - g(d_i + 1) = \frac{n}{m} \sum_{i=1}^{k} d_i = n$$$, thus satisfies (**).
Solving for $$$g$$$ gives $$$g(x) = -\frac{n}{m}\frac{x(x-1)}{2} = -\frac{n}{m} \binom{x}{2}$$$.
Finally, $$$f(S) = c - \frac{n}{m} \sum_{i=1}^{k} \binom{d_i + 1}{3}$$$.
In order to satisfy (*), we need to choose $$$c = \frac{n}{m} \binom{m + 1}{3}$$$.