这题……我一般数位dp都是直接用一个dp把所有东西算完，然而……多组询问每次重新dp会T……然后只好先预处理再查询，然后还搞不了k=0，只好再单独写一个dp……烦死了……
k!=0时，数位的乘积总共就几万种，离散化再预处理转移。f[i][j]表示前i位，乘积为j。k==0时，f[i][2][2][2][2]表示第i位，是否卡下界，是否卡上界，乘积是否为0，是否全是前导0。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=20120427;
const int M=20;
const int N=6e4;
int n,q,z1[N][10],z2[N][10];
ll x,y,k,e[M]={1},z3[N],f[M][N][2];
int sol(int r1,ll r2){
int m=0,r3[M],r4=0;
for(ll i=r2;i;i/=10)
r3[m++]=i%10;
for(int i=1;i<m;++i)
r4=(r4+f[i][r1][1])%p;
for(int i=m-1;~i;--i){
ll r5=r2/e[i+1]*10;
for(int j=1;j<r3[i];++j)
if(~z2[r1][j]){
ll*r6=f[i][z2[r1][j]];
r4=(r4+r6[1]+(r5+j)*e[i]%p*r6[0])%p;
}
r1=z2[r1][r3[i]];
if(!~r1)break;
}
return r4;
}
int cal(ll i){
return lower_bound(z3,z3+n,i)-z3;
}
namespace ns1{
int m,z1[M],z2[M],f[M][2][2][2][2][2];
void sol(){
for(--x,++y,m=0;y;++m){
z1[m]=x%10,x/=10;
z2[m]=y%10,y/=10;
}
for(int i=m;i<M;++i)
z1[i]=z2[i]=0;
memset(f,0,sizeof f);
f[m][1][1][0][1][0]=1;
for(int a=m-1;~a;--a)
for(int b=1;~b;--b)
for(int c=1;~c;--c){
int u=b?z1[a]:0,v=c?z2[a]:9;
for(int d=1;~d;--d){
int(*s)[2]=f[a+1][b][c][d];
for(int e=u;e<=v;++e){
int(*t)[2][2]=f[a][b&e==z1[a]][c&e==z2[a]];
(t[d|!e][0][0]+=s[0][0])%=p;
(t[d|!e][0][1]+=s[0][1]*10+e*s[0][0])%=p;
(t[0][!e][0]+=s[1][0])%=p;
(t[0][!e][1]+=e*s[1][0])%=p;
}
}
}
printf("%d\n",f[0][0][0][1][0][1]);
}
}
int main(){
for(int i=1;i<M;++i)
e[i]=e[i-1]*10;
const ll v=16e16;
for(ll a=1;a<v;a*=2)
for(ll b=a;b<v;b*=3)
for(ll c=b;c<v;c*=5)
for(ll d=c;d<v;d*=7)z3[n++]=d;
sort(z3,z3+n);
memset(z1,-1,sizeof z1);
memset(z2,-1,sizeof z2);
for(int j=0;j<n;++j)
for(int i=9;i;--i)
if(z3[j]*i<v)
z2[z1[j][i]=cal(z3[j]*i)][i]=j;
f[0][0][0]=1;
for(int i=0;i<18;++i)
for(int j=0;j<n;++j){
ll*s=f[i][j];
if(!s[0])continue;
s[0]%=p;
for(int k=9;k;--k)
if(~z1[j][k]){
ll*t=f[i+1][z1[j][k]];
t[0]+=s[0];
(t[1]+=s[1]+k*e[i]%p*s[0])%=p;
}
}
scanf("%d",&q);
while(q--){
scanf("%lld%lld%lld",&x,&y,&k);
if(!k)ns1::sol();
else if(k>=v)puts("0");
else{
int j=cal(k);
if(z3[j]!=k)puts("0");
else
printf("%d\n",(sol(j,y+1)-sol(j,x)+p)%p);
}
}
}