Count the Number of Infection Sequences

Sort the initially sick positions and count healthy people in the gaps they create. The healthy people before the first sick index and after the last can only be infected from one side, while an internal gap of length g can be infected from either end; its internal orders contribute 2^(g-1). Across all gaps, interleave their infection events using factorial(totalHealthy) divided by factorial(gapLength) for every gap, all modulo the required prime. Precompute factorials and inverse factorials once, then multiply the end-gap and internal-gap contributions carefully. Explain why internal gaps have two expanding fronts while edge gaps have one. Check no healthy people, adjacent sick people, and a single initial sick person. With n people, sorting is O(m log m) for m sick indices and preprocessing is O(n) time/space.