<p>You are given an integer <code>n</code> and an array <code>sick</code> sorted in increasing order, representing positions of infected people in a line of <code>n</code> people.</p>

<p>At each step, <strong>one </strong>uninfected person <strong>adjacent</strong> to an infected person gets infected. This process continues until everyone is infected.</p>

<p>An <strong>infection sequence</strong> is the order in which uninfected people become infected, excluding those initially infected.</p>

<p>Return the number of different infection sequences possible, modulo <code>10<sup>9</sup>+7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 5, sick = [0,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<p>There is a total of 6 different sequences overall.</p>

<ul>
	<li>Valid infection sequences are <code>[1,2,3]</code>, <code>[1,3,2]</code>, <code>[3,2,1]</code> and <code>[3,1,2]</code>.</li>
	<li><code>[2,3,1]</code> and <code>[2,1,3]</code> are not valid infection sequences because the person at index 2 cannot be infected at the first step.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 4, sick = [1]</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>There is a total of 6 different sequences overall.</p>

<ul>
	<li>Valid infection sequences are <code>[0,2,3]</code>, <code>[2,0,3]</code> and <code>[2,3,0]</code>.</li>
	<li><code>[3,2,0]</code>, <code>[3,0,2]</code>, and <code>[0,3,2]</code> are not valid infection sequences because the infection starts at the person at index 1, then the order of infection is 2, then 3, and hence 3 cannot be infected earlier than 2.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= sick.length &lt;= n - 1</code></li>
	<li><code>0 &lt;= sick[i] &lt;= n - 1</code></li>
	<li><code>sick</code> is sorted in increasing order.</li>
</ul>

from typing import *


class Solution:
    def numberOfSequence(
        self,
        n: int,
        sick: List[ int ]
        ) -> int:
        
        left_uninfected_block_size = sick[0]
        middle_uninfected_blocks = []
        right_uninfected_block_size = n-1 - sick[-1]
        
        big_prime = 10**9+7
        
        total_nb_of_uninfected = left_uninfected_block_size + right_uninfected_block_size
        
        for i in range( len(sick) - 1 ):
            if sick[i+1] - sick[i] > 1:
                middle_uninfected_blocks.append(sick[i+1] - sick[i] - 1)
                total_nb_of_uninfected += sick[i+1] - sick[i] - 1
                
        nb_of_sequences_without_chrono_order = 1
        
        for block_size in middle_uninfected_blocks:
            for _ in range( block_size - 1 ):
                nb_of_sequences_without_chrono_order = (
                    (nb_of_sequences_without_chrono_order * 2) % big_prime
                )
                
        nb_of_remaining_uninfected_blocks = total_nb_of_uninfected
        dividend = 1
        divisor = 1
        
        for block_size in middle_uninfected_blocks + [
            x
            for x in [ left_uninfected_block_size, right_uninfected_block_size ]
            if x
            ]:
            
            for dividend_i in range(
                nb_of_remaining_uninfected_blocks - block_size + 1,
                nb_of_remaining_uninfected_blocks + 1
                ):
                
                dividend = (
                    (dividend * dividend_i) % big_prime
                )
                
            for divisor_i in range(1, block_size+1):
                divisor = (
                    (divisor * divisor_i) % big_prime
                )
                
            nb_of_remaining_uninfected_blocks -= block_size
        
        # inversion of divisor_i
        inverse_of_divisor = pow(divisor, -1, 10**9+7)
        
        nb_of_orderings = (dividend * inverse_of_divisor) % big_prime
        
        return (nb_of_sequences_without_chrono_order * nb_of_orderings) % big_prime
3398