非常神的数位dp，我调了几乎一天
首先和bzoj3131类似，乘积是可以预处理出来的，注意这里乘积有一个表示的技巧
因为这里质因数只有2,3,5,7，所以我们可以表示成2^a*3^b*5^c*7^d，也就是v[a,b,c,d]这个数组
这样也非常方便进行除法，乘法的状态转移，转移和要维护的东西比较多，我就直接在程序里注释了
这里维护转移的核心思想是算每一位对编号和的贡献，乘积为0和非0分开计算
const mo=;
lim=;
q:array[..,..] of longint=((,,,),(,,,),(,,,),(,,,),(,,,),
(,,,),(,,,),(,,,),(,,,));
//~对乘积的影响
var v:array[..,..,..,..] of longint;
f,s:array[..,..] of longint;
p,r,g,h:array[..] of longint;
pp:array[..] of int64;
n,a,b,c,d,i,j,t,m,k:longint;
x,y,w:int64; procedure up(var a:longint; b:longint);
begin
a:=(a+b+mo) mod mo;
end; procedure pre;
var i,j,k,p:int64;
a,b,c,d:longint;
begin
i:=;
a:=;
while i<=lim do
begin
j:=i; b:=;
while j<=lim do
begin
k:=j; c:=;
while k<=lim do
begin
p:=k; d:=;
while p<=lim do
begin
inc(t);
v[a,b,c,d]:=t;
p:=p*;
inc(d);
end;
k:=k*;
inc(c);
end;
j:=j*;
inc(b);
end;
i:=i*;
inc(a);
end;
end; procedure work;
var a,b,c,d,i,j:longint;
begin
f[,]:=;
for i:= to do
for a:= to do for b:= to do for c:= to do for d:= to do
if (v[a,b,c,d]>) and (f[i-,v[a,b,c,d]]>) then
begin
for j:= to do
begin
up(f[i,v[a+q[j,],b+q[j,],c+q[j,],d+q[j,]]],f[i-,v[a,b,c,d]]);
//f[i,S]表示i位数乘积为S的数的个数
up(s[i,v[a+q[j,],b+q[j,],c+q[j,],d+q[j,]]],s[i-,v[a,b,c,d]]+int64(f[i-,v[a,b,c,d]])*int64(j)*int64(p[i]) mod mo);
//s[i,S]表示i位数乘积为S的数的和，转移就是算当前第i位对和的贡献，显然是j(第i位的数)*p[i](位权)*f[i-,S/j]
end;
end
else if v[a,b,c,d]= then break;
h[]:=;
for i:= to do
begin
h[i]:=h[i-]* mod mo; //i位数不含0的个数
g[i]:=(g[i-]*+*int64(p[i])*int64(h[i-]) mod mo) mod mo; //i位数不含0的数的和，=+..+
end;
end; procedure get(x:int64);
begin
m:=;
while x> do
begin
inc(m);
r[m]:=x mod ;
x:=x div ;
end;
end; function can(x:int64):boolean;
begin
a:=; b:=; c:=; d:=; //拆分成2^a*^b*^c*^d
while x mod = do
begin
inc(a);
x:=x div ;
end;
while x mod = do
begin
inc(b);
x:=x div ;
end;
while x mod = do
begin
inc(c);
x:=x div ;
end;
while x mod = do
begin
inc(d);
x:=x div ;
end;
if x= then exit(true) else exit(false);
end; function sum(a:int64):longint; //防止爆int64的计算
var b:int64;
begin
b:=a-;
if a mod = then a:=a div
else b:=b div ;
a:=a mod mo;
b:=b mod mo;
exit(a*b mod mo);
end; function count(x,k:int64):longint;
var i,j,pre,a1,b1,c1,d1,ans:longint;
now:int64;
begin
if not can(k) then exit(); //k不存在
get(x);
ans:=;
for i:= to m- do //统计1~m-位数乘积为k数的和
up(ans,s[i,v[a,b,c,d]]);
now:=;
pre:=; //pre=∑(r[i]*p[i])
for i:=m downto do
begin
now:=now*int64(r[i]);
if r[i]= then break; //显然
for j:= to r[i]- do
begin
a1:=a-q[j,]; b1:=b-q[j,]; c1:=c-q[j,]; d1:=d-q[j,];
if (a1<) or (b1<) or (c1<) or (d1<) then continue;
up(ans,s[i-,v[a1,b1,c1,d1]]+int64(pre+j*p[i])*int64(f[i-,v[a1,b1,c1,d1]]) mod mo);
//和与处理的转移类似
end;
a:=a-q[r[i],]; b:=b-q[r[i],]; c:=c-q[r[i],]; d:=d-q[r[i],];
up(pre,r[i]*p[i] mod mo);
if (a<) or (b<) or (c<) or (d<) then break;
end;
if now=k then up(ans,x mod mo); //判断x
exit(ans);
end; function calc(x:int64):longint; //乘积为0的转移要复杂，容易出错
var i,j,pre,ans,e:longint;
begin
get(x);
ans:=sum(p[m]) mod mo; //先求1~m-乘积为0的数和，我们可以用补集的思想，总和-不含0的数和
for i:= to m- do
up(ans,-g[i]);
pre:=;
for i:=m downto do
begin
if r[i]= then
begin
up(ans,int64(pre)*int64(x mod pp[i] mod mo+) mod mo+sum(x mod pp[i]+));
//当前为0，后面对答案的贡献可以直接算出来
break;
end;
if i<m then up(ans,int64(pre)*int64(p[i]) mod mo+sum(pp[i]));
//否则m位数且小于等于x的数当前位可以是0，计算贡献
if i= then e:=r[i] else e:=r[i]-;
for j:= to e do
up(ans,sum(pp[i])-g[i-]+int64(pre+j*p[i])*int64((p[i]-h[i-]+mo) mod mo) mod mo);
//这里还是运用到补集的思想，和之前算乘积不为0类似
up(pre,r[i]*p[i] mod mo);
end;
exit(ans);
end; begin
readln(n);
p[]:=;
pp[]:=;
for i:= to do
begin
p[i]:=p[i-]* mod mo; //位权
pp[i]:=pp[i-]*;
end;
pre;
work;
for i:= to n do
begin
readln(x,y,w);
if w= then writeln((calc(y)-calc(x-)+mo) mod mo)
else writeln((count(y,w)-count(x-,w)+mo) mod mo);
end;
end.