Expected Number of Customers

All submissions for this problem are available.

### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK112/hindi/MMNN01.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK112/mandarin/MMNN01.pdf), [Russian](http://www.codechef.com/download/translated/COOK112/russian/MMNN01.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK112/vietnamese/MMNN01.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK112/bengali/MMNN01.pdf) as well. A cake consists of $N$ pieces arranged in a row. Each piece has one of $M$ distinct flavours (numbered $1$ through $M$) which are available in Chef's kitchen. For each valid $i$, the cost of the $i$-th flavour is $i$ rupees. When Chef bakes a cake, he chooses the flavour of each piece independently and uniformly randomly from these $M$ flavours. After baking the cake, he splits it into several contiguous segments (each piece must belong to exactly one segment) and sells each segment to a different customer. The price of a segment is the sum of costs of all distinct flavours of the pieces in that segment. For example, the cost of a segment with flavours $(1, 2, 1, 5)$ is $1+2+5=8$. Chef's profit is the sum of prices of all segments. Chef is very greedy, so he wants to maximise his profit, but he is also a perfectionist, so he wants to split the cake into the minimum number of segments such that his profit is still the largest possible. Chef is wondering about the number of customers he would be able to serve. Help him find the expected value of the number of segments he would split a cake into. It can be proved that this expected value can be expressed as a fraction $p/q$, where $p$ and $q$ are positive integers and $q$ is coprime to $10^9+7$. You should find $p \cdot q^{-1}$ modulo $10^9+7$, where $q^{-1}$ denotes the multiplicative inverse of $q$ modulo $10^9+7$. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first and only line of each test case contains two space-separated integers $N$ and $M$. ### Output For each test case, print a single line containing one integer $p \cdot q^{-1}$ modulo $10^9+7$. ### Constraints - $1 \le T \le 2 \cdot 10^5$ - $1 \le N \le 2 \cdot 10^5$ - $1 \le M \le 10^9$ - the sum of $N$ over all test cases does not exceed $2 \cdot 10^5$ ### Example Input ``` 2 4 2 5 6 ``` ### Example Output ``` 875000009 948302478 ``` ### Explanation **Example case 1:** For the following sequences of flavours, the cake can be divided into: - 2 segments: $(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1)$ - 3 segments: $(1,1,1,2),(1,1,2,1),(1,1,2,2),(1,2,1,1),(1,2,2,2),(2,1,1,1),(2,1,2,2),(2,2,1,1),(2,2,1,2),(2,2,2,1)$ - 4 segments: $(1,1,1,1),(2,2,2,2)$ The expected value of the number of segments is $(2 \cdot 4 + 3 \cdot 10 + 4 \cdot 2) / 16 = 23/8$.