N. New Randomized Go
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

The game of go was thought to be among the last to see computer vs human competition becoming pointless because of humiliation of the former. Alas, AlphaGo was there to tear apart the hopes of the community and Lee Sedol is now looking for new ways to compete with someone at something. He came up with a randomized version of the game that asks for no thinking at all, only pure luck is required. Moreover, this new game is for one player only!

Consider the circle of integer perimeter $$$l$$$. Introduce a coordinate system along the circumference so that any its point is assigned a real value $$$x$$$, $$$0 \leq x \lt l$$$. We are given $$$n$$$ distinct points on the circumference, the $$$i$$$-th point has coordinate $$$x_i$$$.

The game process is very simple. The player throws a fair coin $$$n$$$ times and paints each point red or blue depending on the outcome of the corresponding throw. Thus, all points are independently and equiprobably assigned one of these two colors. Then, the players draws a convex hull of all red points and a convex hull of all blue points. Recall that the convex hull of a finite set of points is the smallest convex polygon such that all points of the set lie inside the polygon or on its border.

The player is declared a winner if the center of the circle is a part (lies inside or on the border) of both convex hulls. You are given the parameters of the game before the coin part starts. Compute the probability of a winning game.

Input

The first line contains two integers $$$n$$$ ($$$1 \leq n \leq 1\,000\,000$$$) and $$$l$$$ ($$$n \leq l \leq 10^9$$$).

Then follow a line containing $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$0 \leq x_i \lt l$$$, $$$x_i \neq x_j$$$ for $$$i \neq j$$$) describing the positions of the points along the circumference.

Output

It is guaranteed that the probability of a winning game can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$q$$$ is coprime with $$$10^9 + 7$$$. Your goal is to find such integer $$$r$$$ ($$$0 \leq r \lt 10^9 + 7$$$) that $$$r \cdot q \equiv p \pmod{10^9+7}$$$.

Examples
Input
4 100
0 30 50 80
Output
125000001
Input
8 100
1 12 34 45 51 84 88 92
Output
515625004
Note

Probability is $$$\frac{1}{8}$$$ in the first test case and $$$\frac{25}{64}$$$ in the second test case.