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: TotalPerson InfectedPerson↵
Space Seperated InfectedPerson Indexes↵
↵
Output: ↵
No of possible sequences↵
↵
↵
TestCase:↵
↵
Input:↵
5 2↵
#### 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 ↵
↵
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: TotalPerson InfectedPerson↵
Space Seperated InfectedPerson Indexes↵
↵
Output: ↵
No of possible sequences↵
↵
↵
TestCase:↵
↵
Input:↵
#### 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 ↵
