How to solve this?

Правка en5, от CO_OS_THOC, 2021-05-23 12:38:56

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский CO_OS_THOC 2021-05-23 12:38:56 110
en4 Английский CO_OS_THOC 2021-05-23 10:00:49 58
en3 Английский CO_OS_THOC 2021-05-23 09:58:44 15 Reverted to en1
en2 Английский 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 Английский CO_OS_THOC 2021-05-23 09:53:06 1908 Initial revision (published)