B. Collecting Cards
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Manuel is a big fan of "Magic: The Gathering" and is always looking to expand his collection. Recently, he has watched a lot of videos of pack openings, and would like to start doing some himself.

Currently, Manuel doesn't have a lot of money, so he needs to leverage the free "booster" packs that he can get at his local comic book shop. These packs contain a single card, and it can be any of the $$$N$$$ available cards in the market right now. Each card can be uniquely identified by it's 'release" number. All of the $$$N$$$ cards have the same probability to show up in a pack.

Manuel has seen that some videos seem to get more views than others, so he has devised a strategy for his to go viral. He has picked a sequence of $$$K$$$ popular release numbers that he wants to capture in the video. He needs this sequence to show up in a continuous way while he opens packs, that means no gaps or other numbers between the desired sequence.

As to not make a lot of trips to the comic book store, he would like to know what's the expected number of packs that he will need to open until he gets his desired continuous sequence of release numbers.

Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N \leq 10^{18}; 1 \leq K \leq 10^6$$$) – the number of available cards and the length of the desired sequence.

Next line contains $$$k$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq N$$$) separated by a space – the unique identifier assigned to each card.

Output

Print a single integer – the expected number of packs you have to open in order to obtain the desired sequence of cards. It can be shown that this can be represented by $$$P / Q$$$, where $$$P$$$ and $$$Q$$$ are coprime integers. Print the value of $$$P \times Q^{-1}$$$ $$$(mod$$$ $$$10^9+7)$$$

Examples
Input
10 13
1 2 10 5 5 2 4 10 1 5 4 6 7
Output
999930007
Input
2 5
1 1 2 2 1
Output
34