409237: GYM103464 D A Task With Queries

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:

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$$$.