Александр просит вас решить следующую задачу:
У него есть массив $$$a$$$ из $$$n$$$ целых положительных чисел. Теперь он хочет, чтобы вы ответили на $$$q$$$ запросов. В $$$i$$$-м запросе подаются два целых положительных числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$). Александр просит вас назвать количество делителей числа $$$a_{l_i} \cdot a_{l_i + 1} \cdot \ldots \cdot a_{r_i}$$$, то есть количество делителей у произведения чисел на отрезке $$$[l_i, r_i]$$$.
Так как ответы могут быть очень большими, выводите их по модулю $$$10^9 + 7$$$.
В первой строке расположены два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 10^5, 1 \le q \le 10^5$$$) — количество чисел и запросов соответственно.
Во второй строке находятся $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^7$$$) — элементы массива $$$a$$$.
Далее в $$$q$$$ строках заданы по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — параметры $$$i$$$-го запроса.
Выводите ответы на запросы, по одному ответу на запрос в каждой строке.
В этой задаче оценка по подзадачам. Баллы за подзадачу засчитываются, только если все тесты данной подзадачи пройдены. Подзадачи приведены в следующей таблице:
| № | Ограничения | Баллы за подзадачу |
| 1 | $$$n \le 4$$$, $$$a_i \le 100$$$, $$$q \le 10$$$ | 9 |
| 2 | $$$n \le 6$$$, $$$a_i \le 500$$$, $$$q \le 10$$$ | 7 |
| 3 | $$$a_i \le 10^5$$$, $$$l_i = r_i$$$ | 8 |
| 4 | $$$l_i = r_i$$$ | 9 |
| 5 | $$$n \le 100$$$, $$$a_i \le 10^4$$$, $$$q \le 100$$$ | 14 |
| 6 | $$$n \le 3000$$$, $$$a_i \le 10^5$$$, $$$q \le 3000$$$ | 17 |
| 7 | $$$a_i \le 100$$$ | 14 |
| 8 | $$$a_i \le 10^5$$$ | 9 |
| 9 | Нет дополнительных ограничений | 13 |
7 5 4 6 1 1 5 12 9 1 7 2 5 3 3 2 5 3 6
60 8 1 8 12
Рассмотрим ответ на пятый запрос. $$$a_3 \cdot a_4 \cdot a_5 \cdot a_6 = 60$$$. Число $$$60$$$ имеет следующие делители: $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$10$$$, $$$12$$$, $$$15$$$, $$$20$$$, $$$30$$$, $$$60$$$.
