Alexander asks you to solve the following problem:
He has an array $$$a$$$ of $$$n$$$ positive integers. Now he wants you to answer $$$q$$$ queries. The $$$i$$$-th query contains two positive integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$). Alexander asks you to find the number of divisors of $$$a_{l_i} \cdot a_{l_i + 1} \cdot \ldots \cdot a_{r_i}$$$, that is, the number of divisors of the product of numbers on the segment $$$[l_i, r_i]$$$.
Since the answers can be very large, print them modulo $$$10^9 + 7$$$.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^5, 1 \le q \le 10^5$$$) —the number of numbers and queries, respectively.
The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^7$$$) — elements of the array $$$a$$$.
Then $$$q$$$ lines each contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — parameters of $$$i$$$th query.
Print query responses, one response per query in separate line.
In this problem there is a subtask scores. Score for a subtask are counted only if all tests for that subtask are passed. The subtasks are listed in the following table:
| № | Constraints | Scores for the subtask |
| 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 | No additional constraints | 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
Consider the answer to the fifth query. $$$a_3 \cdot a_4 \cdot a_5 \cdot a_6 = 60$$$. The number $$$60$$$ has the following divisors: $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$10$$$, $$$12$$$, $$$15$$$, $$$20$$$, $$$30$$$, $$$60$$$.
