Product Except Self Modulo M

Challenge

For each position i, return the product of all nums[j] with j ≠ i, reduced modulo modulus. Return a list of residues from 0 to modulus-1. The modulus is not necessarily prime, and numbers can be zero or negative. Use prefix/suffix products rather than division.

Input and output contract

0 ≤ n ≤ 3,500; |nums[i]| ≤ 1,000,000; 2 ≤ modulus ≤ 1,000,000,007. The product over no elements is 1, so a singleton returns [1]; empty input returns [].

All tests follow this contract. You do not need to validate malformed input. Return the requested result from product_except_self; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.

Target complexity: O(n) arithmetic operations; O(1) auxiliary space excluding output

Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.

Public examples

[[2, 3, 4], 12]

[0, 8, 6]

[[0, -2, 3], 7]

[1, 0, 0]

[[9], 8]

[1]

The worked solution unlocks after completion, or with Premium access.