WA:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int t,k,maxn[1010],len,f[1010][1010][2];
//char l[1010],r[1010];
string l,r;
int dfs(int x,int last,bool flag,bool done)
{
	if(!x)
	return done;
	if(!flag&&f[x][last][done]!=-1)
	return f[x][last][done];
	int lim=flag?maxn[x]:9,sum=0;
	for(int i=0;i<=lim;i++)
	if(i==4||i==7)
	sum=(sum+dfs(x-1,x,flag&&i==lim,done||(last&&last-x<=k)))%mod;
	else
	sum=(sum+dfs(x-1,last,flag&&i==lim,done))%mod;
	if(!flag)
	f[x][last][done]=sum;
	return sum;
}
//int ask(char s[])
int ask(string s)
{
//	int n=strlen(s);
	int n=s.size();
	for(int i=1;i<=n;i++)
	maxn[i]=s[n-i]-'0';
	return dfs(n,0,1,0);
}
//bool check(char s[])
bool check(string s)
{
//	int n=strlen(s),last=-2000;
	int n=s.size(),last=-2000;
	for(int i=0;i<n;i++)
	if(s[i]=='4'||s[i]=='7')
	{
		if(i-last<=k)
		return 1;
		last=i;
	}
	return 0;
}
signed main()
{
	cin>>t>>k;
	memset(f,-1,sizeof(f));
	while(t--)
	{
//		scanf("%s%s",l,r);
		cin>>l>>r;
		cout<<((ask(r)-ask(l)+check(l))%mod+mod)%mod<<endl;
	}
}

A

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int t,k,maxn[1010],len,f[1010][1010][2];
//char l[1010],r[1010];
string l,r;
int dfs(int x,int last,bool flag,bool done)
{
	if(!x)
	return done;
	if(!flag&&f[x][last][done]!=-1)
	return f[x][last][done];
	int lim=flag?maxn[x]:9,sum=0;
	for(int i=0;i<=lim;i++)
	if(i==4||i==7)
	sum=(sum+dfs(x-1,x,flag&&i==lim,done||last-x<=k))%mod;
	else
	sum=(sum+dfs(x-1,last,flag&&i==lim,done))%mod;
	if(!flag)
	f[x][last][done]=sum;
	return sum;
}
//int ask(char s[])
int ask(string s)
{
//	int n=strlen(s);
	int n=s.size();
	for(int i=1;i<=n;i++)
	maxn[i]=s[n-i]-'0';
	return dfs(n,3000,1,0);
}
//bool check(char s[])
bool check(string s)
{
//	int n=strlen(s),last=-2000;
	int n=s.size(),last=-2000;
	for(int i=0;i<n;i++)
	if(s[i]=='4'||s[i]=='7')
	{
		if(i-last<=k)
		return 1;
		last=i;
	}
	return 0;
}
signed main()
{
	cin>>t>>k;
	memset(f,-1,sizeof(f));
	while(t--)
	{
//		scanf("%s%s",l,r);
		cin>>l>>r;
		cout<<((ask(r)-ask(l)+check(l))%mod+mod)%mod<<endl;
	}
}