infection_combinations2.py

from collections import Counter
from typing import List

MODULO_BASE = 10**9 + 7


def infected_combination(n: int, infectedHouses: List[int]) -> int:
    if len(infectedHouses) == 0:
        return 0
    sequences = []
    if infectedHouses[0] > 0:
        sequences.append(infectedHouses[0])
    if infectedHouses[-1] < n - 1:
        sequences.append(n - 1 - infectedHouses[-1])

    for a, b in zip(infectedHouses, infectedHouses[1:]):
        size = b - a - 1
        if size > 0:
            sequences.append(size // 2)
            sequences.append(size // 2)

    sequences_counter = Counter(sequences)
    num_sequences = len(sequences)
    total = 1
    offset = 0
    print(sequences)
    print(sequences_counter)
    for size, count in sorted(sequences_counter.items(), key=lambda x: x[0]):
        total *= num_sequences ** (size - offset)
        num_sequences -= count
        offset = size

    return total % MODULO_BASE


print(infected_combination(8, [0, 6]))