An Infectious disease is spreading in a city. The Mayor of the city wants to take strict actions to provide proper prevention from the disease
There are N persons in the city who stey side by side in increasing order of their index that is, the person ith person has the (i-1)th and (i+1)th staying next to him or her.
Initially, it is found that among N persons, exactly M are infected with the disease. Further, it was found the disease is contagious and it spreads from en infected person to his or her neighbors. It means that if the ith person is infected, then the (i-1)th person and (i + 1)th person staying just next to the person can get infected from him or her.
Also is observed that people who are not infected (people apart from initial M infected people) get infected in a particular sequence. This sequence provides the ordere in which people(who are not infected initially) gets infected with the increasing span of time. It may be possible that xth person gets infected only after the yth person and this defines a particular order among them, that is y must always be placed before x in the sequence.
For example, N = 6 and person 3 and 5 are infected. Here, person 2 gets affected before person 1. Simarly person 2 and 4 can be placed with any relative order as they can get infected from 3 directly.
The Mayor wants you to determine the number of unique sequences in which the other persons can get infected. Since the answer can be large print modulo 1000000007
Input: First line contains 2 space separated integers N & M. Next line contains M space separated integers denoting infected people.
Output: No of possible sequences
TestCase:
Input:
5 2
1 5
Output: 4
Explaination: Person 2 & 4 can get infected from person 1 & 5. Person 3 can only get infected after either Person 2 or Person 4 gets infected.
The possible sequences: [2,3,4] [2,4,3] [4,3,2] [4,2,3]
Constraints: 1 <= N <= 2e5 1 <= M <= N -1
