#include<bits/stdc++.h>
using namespace std;
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld%lld",&x,&y)
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pf(x) printf("%lld",x)
#define pii pair<int,int> 
#define s second
#define int long long



//
//
const int mod = 1e9+7;
string ss;
map<int,int> mp[5];
int op[5]={0,9000,35,11,9};

void caozuo(int u)
{
	if(!mp[u].size()) return ;
	
	for(int i=1;i<=op[u-1];i++)
	{
		int now =i;
		int sum=0;
		while(now)
		{
			sum+=now%10;
			now/=10;
		}
		if(mp[u].count(sum)) mp[u-1][i]=1;
	}
}
int f[1010][9010];

void init()
{
	f[0][0]=1;
	for(int i=1;i<=1000;i++)
		for(int j=0;j<=9000;j++){
			for(int k=0;k<=9;k++)
				if(j>=k) f[i][j]=(f[i][j]+f[i-1][j-k])%mod;
			}
}

int dp(int x)
{
	int last=0,sum=0;
	for(int i=0;i<ss.size();i++)
	{
		int n = ss[i]-'0';
		for(int j=0;j<n;j++){
			if(x-last-j>=0)
			sum=(sum+f[ss.size()-i-1][x-last-j])%mod;
		}
		last+=n;
		if(i==(int)ss.size()-1) if(last==x) sum=(sum+1)%mod;
	}
	return sum%mod;
}

void solve()
{
	for(int i=0;i<=4;i++) mp[i].clear();
	int m,k;
	cin>>ss>>m>>k;
	if(m>4) m=4;
	mp[m][k]=1;
	for(int i=4;i>=2;i--)
	caozuo(i);
	
	int res=0;
	for(auto [x,y]:mp[1])
		res=(res+dp(x))%mod;
	cout<<res<<endl;
}
signed main()
{
	init();
	IOS;
	int _=1;
	cin>>_;
	while(_--)
		solve();
	return 0;
}