Divisor Count Queries

Given a sequence of length \(n\) and \(m\) queries, each query asks for the number of divisors of the product of a subarray modulo \(19260817\). For a subarray query from \(l\) to \(r\), let the product be \(P = a_l \times a_{l+1} \times \cdots \times a_r\). If the prime factorization of \(P\) is given by \(P = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\), then the number of divisors is \( (e_1+1)(e_2+1)\cdots(e_k+1) \).

inputFormat

The first line contains two integers \(n\) and \(m\). The second line contains \(n\) integers representing the sequence. Each of the next \(m\) lines contains two integers \(l\) and \(r\) (1-indexed), indicating a query.

outputFormat

For each query, output a single integer: the number of divisors of the product of the subarray from \(l\) to \(r\) modulo \(19260817\).

sample

5 3
2 3 4 6 7
1 3
2 5
1 5

8
24
30