Abode the wizard (Ammar's friend who lives in Hate-matrix land) is on vacation. He found an infinite street that has $$$n$$$ trees , tree $$$i$$$ is $$$a_i$$$ meters away from the beginning of the street, and all the trees are $$$h$$$ meters tall.
Abode started walking from the beginning of the street. When he passes near a tree, he does nothing if it is already fallen. Otherwise, he casts a spell and one of the following events happens, all in equal probability:
When a tree in position $$$x$$$ falls to the right, all standing trees in positions $$$[x,x+h]$$$ will fall to the right. Similarly, if it fell to the left, all standing trees in positions $$$[x-h,x]$$$ will fall to the left.
Now Abode wonders, what is the expected value of the sum of heights of the standing trees after he passes near all the trees? Print it Modulo $$$10^9+7$$$.
Formally, let $$$M=10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q\not\equiv 0(mod M)$$$. Output the integer equal to $$$p \cdot q^{-1} mod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \leq x \lt M$$$ and $$$x \cdot q \equiv p (mod M)$$$.
The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$ — the number of testcases.
The first line of each testcase consists of two integers $$$n,h \: (1 \leq n \leq 2 \cdot 10^5) (1 \leq h \leq 10^9)$$$— the number of trees and their height.
The second line of each testcase consists of $$$n$$$ integers $$$a_i \: (1 \leq a_i \leq 10^9) (a_i \lt a_{i+1})$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.
For each testcase, print the expected value of the sum of heights of standing trees modulo $$$10^9+7$$$.
32 101 1012 101 25 101 3 4 5 25
666666678 444444452 716049396
