数位 dp 板子。为啥是紫？为啥是紫？为啥是紫？
记录上一个幸运数字距离多少，是否达到上界，多测只能记忆化剩下 \(len\) 位且未达到上界的情况。剩下的就是分讨。
\(calc(r)-calc(l-1)\)，\(l-1\) 很麻烦，学习题解的直接 \(O(len)\) \(check\) 一下 \(l\) 变为 \(calc(r)-calc(l)+check(l)\) 即可。
Takanashi Rikka
// Problem: CF95D Horse Races
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF95D
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define intz(x,z) memset((x),(z),sizeof((x)))
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
inline ll lowbit(ll x){return x&-x;}
#define fi first
#define se second
inline void cmx(auto &x,ll y){if(y>x)x=y;}
inline void cmn(auto &x,ll y){if(y<x)x=y;}
const int N=1005,mod=1e9+7;
int k,w[N][N];ll pw[N],sum[N];
char l[N],r[N];
int dfs(char *s,int len,int u,int p,bool f){if(u==len+1)return 0;int t=(p==-1?0:p);if(f&&w[len-u][t]!=-1)return w[len-u][t];ll res=0;int mx=(f?9:s[u]-'0');if(p!=-1&&p<=k){if(mx>=7)(res+=((f|(mx>7))?pw[len-u]:sum[u+1]+1))%=mod;if(mx>=4)(res+=((f|(mx>4))?pw[len-u]:sum[u+1]+1))%=mod;}else{if(mx>=7)(res+=dfs(s,len,u+1,1,f|(mx>7)))%=mod;if(mx>=4)(res+=dfs(s,len,u+1,1,f|(mx>4)))%=mod;}(res+=1ll*(mx-(mx-1>=7)-(mx-1>=4))*dfs(s,len,u+1,(p==-1?-1:p+1),1))%=mod;if(mx!=4&&mx!=7)(res+=dfs(s,len,u+1,(p==-1?-1:p+1),f))%=mod;if(f)w[len-u][t]=res;return res;
}
bool check(char *s,int len){int p=0;for(int i=1;i<=len;i++)if(s[i]=='4'||s[i]=='7'){if(p&&i-p<=k)return 1;p=i;}return 0;
}
void UesugiErii(){cin>>(l+1)>>(r+1);int L=strlen(l+1),R=strlen(r+1);intz(sum,0);for(int i=L;i;i--)sum[i]=(sum[i+1]+pw[L-i]*(l[i]-'0')%mod)%mod;ll ans=(mod-dfs(l,L,1,-1,0))%mod;intz(sum,0);for(int i=R;i;i--)sum[i]=(sum[i+1]+pw[R-i]*(r[i]-'0')%mod)%mod;ans=(ans+dfs(r,R,1,-1,0))%mod;cout<<(ans+check(l,L))%mod<<'\n';
}
signed main(){cfast;intz(w,-1);for(int i=pw[0]=1;i<=1000;i++)pw[i]=pw[i-1]*10%mod;int _=1;cin>>_>>k;for(;_;_--)UesugiErii();return 0;
}