How to solve this?

Revision en4, by CO_OS_THOC, 2021-05-23 10:00:49

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

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English CO_OS_THOC 2021-05-23 12:38:56 110
en4 English CO_OS_THOC 2021-05-23 10:00:49 58
en3 English CO_OS_THOC 2021-05-23 09:58:44 15 Reverted to en1
en2 English CO_OS_THOC 2021-05-23 09:55:26 15 Tiny change: 'ut:\n5 2\n===\n1 5\n===\n\n\nOutp' -> 'ut:\n5 2\n#### \n1 5\n####\n\n\nOutp'
en1 English CO_OS_THOC 2021-05-23 09:53:06 1908 Initial revision (published)