Tích bỏ một, không dùng phép chia

Cho mảng $a_1,a_2,\dots ,a_n$. Với mỗi vị trí $i$ từ $1$ tới $n$, gọi $P_i$ là tích của tất cả các phần tử của mảng trừ $a_i$: $$P_i=\prod _{j\ne i}{a}_j.$$

Hãy tính dãy $P_1,P_2,\dots ,P_n$ theo mô-đun ${10}^9+7$.

Lưu ý quan trọng: Lời giải không được sử dụng phép chia (kể cả nghịch đảo mô-đun). Lý do: nếu có $a_i=0$ thì mọi $P_j$ với $j\ne i$ đều bằng $0$ trên trường ${\mathbb{Z}}_M$ và việc "chia $0$" không hợp lệ. Cách tiếp cận đúng là dùng tiền tố và hậu tố.

Dữ liệu vào

• Dòng đầu: số nguyên $n$.
• Dòng thứ hai: $n$ số nguyên $a_1,\dots ,a_n$, mỗi $a_i$ trong $[0,{10}^9]$.

Dữ liệu ra

Một dòng gồm $n$ số nguyên $P_1,P_2,\dots ,P_n$ cách nhau bởi dấu cách, mỗi số là ${\prod }_{j\ne i}{a}_{j}mod({10}^9+7)$.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $0\le a_i\le {10}^9$

Ví dụ

Ghi chú

• Có thể có nhiều giá trị $0$ trong dãy. Nếu có $\ge 2$ số $0$, mọi $P_i=0$. Nếu có đúng một số $0$ tại vị trí $p$, thì $P_p$ là tích các phần tử $\ne 0$ và mọi $P_i$ với $i\ne p$ đều là $0$.
• Đáp số có thể lớn — luôn lấy mod ${10}^9+7$.