给你一个长为n的序列a
m次查询
每次查询一个区间的所有子区间的gcd的和mod1e9+7的结果
第一行两个数n,m
之后一行n个数表示a
之后m行每行两个数l,r表示查询的区间
对于每个询问，输出一行一个数表示答案
[1,1]的子区间只有[1,1]，其gcd为30
[1,5]的子区间有：
[1,1]=30,[1,2]=30,[1,3]=10,[1,4]=10,[1,5]=10
[2,2]=60,[2,3]=20,[2,4]=20,[2,5]=20
[3,3]=20,[3,4]=20,[3,5]=20
[4,4]=20,[4,5]=20
[5,5]=20
总共330
[2,4]的子区间有：
[2,2]=60,[2,3]=20,[2,4]=20
[3,3]=20,[3,4]=20
[4,4]=20
总共160
[3,4]的子区间有：
[3,3]=20,[3,4]=20
[4,4]=20
总共60
[3,5]的子区间有：
[3,3]=20,[3,4]=20,[3,5]=20
[4,4]=20,[4,5]=20
[5,5]=20
总共120
[2,5]的子区间有：
[2,2]=60,[2,3]=20,[2,4]=20,[2,5]=20
[3,3]=20,[3,4]=20,[3,5]=20
[4,4]=20,[4,5]=20
[5,5]=20
总共240
[2,3]的子区间有：
[2,2]=60,[2,3]=20
[3,3]=20
总共100
对于100%的数据，有1 <= n , m , ai <= 100000