题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5564
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
const int maxn =71;
const int mod=1e9+7;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：统计，长度为l到r之间的，
能被7整除的，且相邻两数之和不为k的，
数字个数（0不算）把dp三维方程列出来，然后把后两维压缩，
压缩成0到70的状态，矩阵幂的形式就构造完成了，
但要求的其实是矩阵乘积的前缀和的形式，
所以要在构造矩阵中加点技巧。
假设要求B+A*B+A^2*B+...
那么可以构造矩阵：
C=| A B || 0 1 |
那么不难发现C矩阵的幂，右上部分就是
上述前缀和数值，直接统计即可。代码毒瘤，，不知道哪里有玄学错误，，和正解对拍后暂时没找到。。。
以后再修改，，如果有大神看出来可以留言交流。时间复杂度：O（logn）。
*/struct mat{ll a[maxn][maxn];mat(){memset(a,0,sizeof(a));for(int i=0;i<maxn;i++) a[i][i]=1;}mat operator*(const mat& y) const{mat ret;for(int i=0;i<maxn;i++) for(int j=0;j<maxn;j++){ret.a[i][j]=0;for(int k=0;k<maxn;k++) ret.a[i][j]=(ret.a[i][j]+1LL*a[i][k]*y.a[k][j]%mod)%mod;}return ret;}
};mat quick_pow(mat x,ll n){mat ret;for(;n;n>>=1,x=x*x) if(n&1) ret=x*ret;return ret;}ll Sta(ll x,ll y) {return 1LL*x*10+1LL*y;}ll l,r,k;
ll solve(ll r){mat x;memset(x.a,0,sizeof(x.a));for(int i=0;i<7;i++){for(int j=0;j<10;j++){for(int p=0;p<10;p++)if(j+p!=k){x.a[Sta((i*10+p)%7,p)][Sta(i,j)]++;}}}for(int i=0;i<10;i++) x.a[Sta(i%7,i)][maxn-1]++;x.a[maxn-1][maxn-1]=1;x=quick_pow(x,r);ll ret=0;for(int i=1;i<10;i++) (ret+=x.a[i][maxn-1])%=mod;return ret;
}int main()
{int t;scanf("%d",&t);while(t--){scanf("%lld%lld%lld",&l,&r,&k);printf("%lld\n",(solve(r)-solve(l-1)+mod)%mod);}return 0;
}