L. Ultimate Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As Pt is devastated with all the academic pressures, she decided to play a game with Kalu for relaxation.

There are two brick walls on the number line at positions $$$0$$$ and $$$N$$$. Some stones are placed on integer positions on the line. There will be exactly one barrier on the line. The barrier is placed on a random position $$$i + 0.5 $$$ where $$$ 0 \le i \lt N$$$. Pt and Kalu will move the rocks in turn following these rules:

  • A player must select a stone to move and move the stone by a positive integer distance.
  • A stone to the left of the barrier can only be moved to the left.
  • A stone to the right of the barrier can only be moved to the right.
  • A stone cannot be moved over any other stone or the walls.
  • Each point can contain at most one stone at a time.
One who can not move any other stone loses the game. The location of the barrier is unknown, and Pt starts the game. Print the probability of Pt winning the game assuming that both players play optimally.

Formally, let the probability be an irreducible fraction $$$\frac{x}{ y}​$$$. Print the value $$$x \cdot y ^ {−1} \bmod{1000000007}$$$. Where $$$y^{-1}$$$ is an integer such that $$$y \cdot y^{-1}≡1 \bmod{1000000007}$$$. We ensure that $$$y^{−1}$$$ exists.

Input

The first line will contain two integers, N and M $$$(2 \le N \le 10^6,0 \le M \lt N)$$$ denoting the position of the right brick wall and the number of stones to move.

The second line of input contains $$$M$$$ space separated unique integers $$$x_1,x_2,x_3,...,x_m$$$$$$(0 \lt x_i \lt N)$$$ denoting the positions of the stones.

Output

Print an integer denoting the probability of Pt winning modulo $$$1000000007$$$.

Examples
Input
2 1
1
Output
0
Input
4 1
2
Output
1
Note

In the first sample, the line can be represented as: |__ * __| Wherever the barrier is, Pt cannot move the stone to any position. So her winning probability is 0.