D. 子序列的和Ⅱ

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

前情回顾:

定义一个数组的权值和为:假设数组乘积为S,数组的权值和为使得x*y=S的所有(x,y)对数(x, y均为正整数)
给你一个数组A,请你求出他的所有非空子序列的权值和,由于答案可能很大,请对998244353取模
例如S=2, 那么就有2对(x, y)符合要求, 分别为(1, 2), (2, 1)

现在小L希望知道某个子数组的权值和,但是他不会做,所以他来询问你了,你能帮帮他吗?
子数组是数组的一段连续区间,例如是数组的子数组

输入格式

第一行两个个整数,代表数组大小和询问个数
第二行个整数,表示给定的数组 接下来行,每行两个整数代表询问的区间

输出格式

对于每个询问,输出一个整数,表示答案

样例

输入样例1

2 1
1 2
1 2

输出样例1

5

数据范围与提示

保证所有均为1或质数