C(n, k), "n choose k", counts the ways to pick k items out of n distinct ones. It is the building block for nearly every counting formula (stars and bars, multiset permutations, inclusion-exclusion sums).
Write pascal(n: int) -> list[list[int]] returning rows 0..n of Pascal's triangle, so that pascal(n)[i][k] == C(i, k) for 0 <= k <= i. Row i has i + 1 entries. Use the recurrence rather than math.comb or factorials:
C(i, 0) = C(i, i) = 1C(i, k) = C(i-1, k-1) + C(i-1, k)for0 < k < i: either itemiis picked (choose the otherk-1from the firsti-1) or it isn't (choose allkfrom the firsti-1).
pascal(0) # [[1]]
pascal(4) # [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
pascal(6)[6][2] # 15: choose 2 of 6
Constraints: 0 <= n <= 500. The numbers get huge; Python ints handle that, so no modulus here.
Show hint
Each row is built from the previous one: [1] + [prev[k-1] + prev[k] for k in range(1, i)] + [1].