[Ynoi2015]此时此刻的光辉

题目背景

难道说... 这么说来...给珂朵莉她们... 正给珂朵莉带来痛苦的是... ![](https://cdn.luogu.com.cn/upload/pic/45561.png) 【威廉?】 【威廉,说真的,你到底怎么了?】 【出什么事了?】 【啊...】 ![](https://cdn.luogu.com.cn/upload/pic/45562.png) 你不慌张吗 【别看我这样,其实我心脏确实有在猛跳】 【但是呢,虽然我不知道发生了什么事】 ![](https://cdn.luogu.com.cn/upload/pic/45563.png) 【可一直爱逞强的你,难得会对我露出软弱的一面嘛~】 【高兴的心情,还有希望你打起精神的心情加在一起】 【要远远胜过惊慌的情绪】 ![](https://cdn.luogu.com.cn/upload/pic/45564.png) 你... 【你刚才,流露着一副要是没人管你就会自己消失的表情哦?】 【虽然非常难为情,但我实在不能撇下你】 ![](https://cdn.luogu.com.cn/upload/pic/45565.png) 你是个...好女人啊... ![](https://cdn.luogu.com.cn/upload/pic/45567.png) 【抱歉,我没有听清楚,再说一遍】 没什么啦... ![](https://cdn.luogu.com.cn/upload/pic/45568.png) 【啊...你还死撑】 【再说一遍,再说一遍就好】 和我结婚吧 ![](https://cdn.luogu.com.cn/upload/pic/45569.png) 【不对...嗯?】 我终于找到了 找到了渴望去保护的人 找到了渴望回去的归宿 觉得自己还可以继续生存下去 总算真切地认识到自己还有继续生存的价值和资格 所以... 我要给你幸福 ![](https://cdn.luogu.com.cn/upload/pic/45570.png) 【嗯】 【我也不会离开你身边的】 【永远,永远和你在一起哦】

题目描述

珂朵莉给你了一个长为 $n$ 的序列,有 $m$ 次查询,每次查询一段区间的乘积的约数个数 $\bmod 19260817$ 的值。

输入输出格式

输入格式


第一行两个整数 $n,m$。 第二行 $n$ 个整数表示这个序列 $a_i$。 之后 $m$ 行,每行两个整数 $l,r$ 表示查询的区间

输出格式


$m$ 行,每行输出一个整数表示答案

输入输出样例

输入样例 #1

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

输出样例 #1

165
15
9
45
10

说明

Idea:will7101,Solution:nzhtl1477,Code:nzhtl1477,Data:nzhtl1477 $1\leq n,m\leq 10^5$,$1 \leq a_i \leq10^9$。