Tích đoạn modular

Cho dãy số nguyên dương $a_1,a_2,\dots ,a_n$ và một số nguyên tố $\text{MOD}={10}^9+7$. Đảm bảo rằng $1\le a_i<\text{MOD}$ với mọi $i$, do đó không có phần tử nào chia hết cho $\text{MOD}$.

Cho $q$ truy vấn. Mỗi truy vấn gồm hai số nguyên $l$ và $r$ ($1\le l\le r\le n$). Với mỗi truy vấn, hãy tính giá trị

$$(a_l·a_{l+1}·\dots ·a_r)mod\text{MOD}.$$

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ cách nhau bởi dấu cách.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l$ và $r$ mô tả một truy vấn.

Dữ liệu ra

In ra $q$ dòng, mỗi dòng là đáp án của truy vấn tương ứng.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le a_i<{10}^9+7$
• $1\le l\le r\le n$

Ví dụ

Ghi chú

$\text{MOD}={10}^9+7$ là số nguyên tố, do đó với mọi $x$ thỏa $1\le x<\text{MOD}$, nghịch đảo modular của $x$ tồn tại và có thể tính bằng định lý nhỏ Fermat: $x^{-1}\equiv x^{\text{MOD}-2}\left(\mathrm{mod}\text{MOD}\right)$.