Product of the Others

Difficulty: 1400 3500 ms 128 MB

prefix-sums

For every position print the product of ALL OTHER elements, modulo 10⁹+7. Division is not available (elements may be 0).

Input: the first line has N; the second line has N integers.

Output: N integers: for each i, ∏_j≠i a_j mod 10⁹+7 (values reduced to [0, mod)).

Constraints:

• 1 ≤ N ≤ 10⁵
• -100 ≤ a_i ≤ 100

Sample Tests

4
1 2 3 4

24 12 8 6

2
0 5

5 0

Read the Editorial