Show problems as
Classic problem #2954HardArrayMathCombinatoricsFermat's Little Theorem

Count the Number of Infection Sequences

Real-world version: Ways the Blight Can Spread
Tracked in this browser only
Read Count the Number of Infection Sequences on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A nursery bench holds n saplings in one straight row, numbered 0 through n - 1. Two saplings are neighbours when their numbers differ by one.

The positions listed in sick, given in increasing order, already carry a blight. Every other sapling is healthy for now. Time passes in rounds, and in each round exactly one healthy sapling that has at least one blighted neighbour catches the blight. When several healthy saplings qualify in a round, any one of them may be the one that catches it. Rounds continue until nothing healthy is left.

A spread order is the list of positions of the initially healthy saplings, written in the order they caught the blight. Return how many different spread orders are possible, taken modulo 1000000007.

Examples

Example 1

Input
n = 5, sick = [0, 4]
Output
4

Saplings 1, 2 and 3 start healthy. One possible spread order is [3, 2, 1]: sapling 3 touches the blighted sapling 4, then sapling 2 touches sapling 3, then sapling 1. Four spread orders are possible altogether.

Example 2

Input
n = 6, sick = [2, 3]
Output
6

Saplings 0, 1, 4 and 5 start healthy. One possible spread order is [1, 4, 5, 0]. An order beginning with sapling 5 is not possible, because in the first round neither neighbour of sapling 5 carries the blight. Six spread orders are possible altogether.

Example 3

Input
n = 9, sick = [4]
Output
70

The blight sits in the middle of the bench with four healthy saplings on either side, and 70 spread orders are possible. One of them is [3, 5, 6, 2, 1, 7, 8, 0].

Constraints

  • 2 <= n <= 10^5
  • 1 <= sick.length <= n - 1
  • 0 <= sick[i] <= n - 1
  • sick is given in strictly increasing order.
  • Return the count taken modulo 1000000007, so the answer is below 1000000007.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def number_of_sequence(n: int, sick: list[int]) -> int:
Java
public int numberOfSequence(int n, int[] sick)

More on the same topics