Background

Could it be...
So that means... for Chtholly and the others...
What is bringing Chtholly pain is...

【William?】
【William, seriously, what happened to you?】
【What’s wrong?】
【Ah...】

Aren’t you panicking?
【Don’t be fooled by how I look, my heart is indeed pounding】
【But, even though I don’t know what happened】

【You, who always like to act tough, are finally showing me a weak side for once~】
【The happiness, and the feeling of wanting you to cheer up, added together】
【Far outweigh the feeling of panic】

You...
【Just now, you had this look like you’d disappear by yourself if nobody cared about you, you know?】
【Although it’s very embarrassing, I really can’t just leave you alone】

You are... a good woman...

【Sorry, I didn’t hear clearly. Say that again.】
It’s nothing...

【Ah... you’re still forcing yourself】
【Say it again. Just say it again.】
Marry me.

【No... huh?】
I finally found it.
I found someone I long to protect.
I found a home I long to return to.
I feel like I can keep living.
At last, I truly realized that I still have the value and the right to keep living.
So...
I will give you happiness.

【Mm.】
【I won’t leave your side either.】
【Forever, forever, I’ll be with you.】

Problem Description

Chtholly gives you a sequence of length $n$. There are $m$ queries. For each query, you need to compute the number of divisors of the product of a subarray, taken $\bmod 19260817$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers, representing the sequence $a_i$.

Then follow $m$ lines, each containing two integers $l, r$, representing the queried interval.

Output Format

Output $m$ lines. Each line contains one integer, the answer to the corresponding query.

5 5
64 2 18 9 100
1 5
2 4
2 3
1 4
3 4

165
15
9
45
10

Hint

Idea: will7101, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477.

Constraints: $1 \leq n, m \leq 10^5$, $1 \leq a_i \leq 10^9$.

Translated by ChatGPT 5