Problem Description

Clarke is a patient with multiple personality disorder. One day, Clarke turned into a researcher, did a research on digits. 
He wants to know the number of positive integers which have a length in [l,r] and are divisible by 7 and the sum of any adjacent digits can not be k.

 

Input

The first line contains an integer T(1≤T≤5), the number of the test cases. 
Each test case contains three integers l,r,k(1≤l≤r≤109,0≤k≤18).

 

Output

Each test case print a line with a number, the answer modulo 109+7.

 

Sample Input

 

Sample Output

 

Source

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<bitset>

#include<set>

#include<map>

#include<time.h>

using namespace std;

#define LL long long

#define bug(x)  cout<<"bug"<<x<<endl;

const int N=5e4+,M=1e6+,inf=1e9+,MOD=1e9+;

const LL INF=1e18+,mod=1e9+;

const double eps=(1e-),pi=(*atan(1.0));

struct Matrix

{

    const static int row=;

    int a[row][row];//矩阵大小根据需求修改

    Matrix()

    {

        memset(a,,sizeof(a));

    }

    void init()

    {

        for(int i=;i<row;i++)

            for(int j=;j<row;j++)

                a[i][j]=(i==j);

    }

    Matrix operator + (const Matrix &B)const

    {

        Matrix C;

        for(int i=;i<row;i++)

            for(int j=;j<row;j++)

                C.a[i][j]=(a[i][j]+B.a[i][j])%MOD;

        return C;

    }

    Matrix operator * (const Matrix &B)const

    {

        Matrix C;

        for(int i=;i<row;i++)

            for(int k=;k<row;k++)

                for(int j=;j<row;j++)

                    C.a[i][j]=(C.a[i][j]+1LL*a[i][k]*B.a[k][j])%MOD;

        return C;

    }

    Matrix operator ^ (const int &t)const

    {

        Matrix A=(*this),res;

        res.init();

        int p=t;

        while(p)

        {

            if(p&)res=res*A;

            A=A*A;

            p>>=;

        }

        return res;

    }

};

Matrix base,one;

void init(int k)

{

    memset(base.a,,sizeof(base.a));

    for(int i=;i<;i++)

    {

        int x=(i/);

        int y=(i%);

        for(int j=;j<;j++)

        {

            int x1=j/;

            int y1=j%;

            if((y+x1*)%==x&&y1+y!=k)

                base.a[j][i]=;

        }

    }

    for(int i=;i<;i++)base.a[i][]=;

    base.a[][]=;

}

int main()

{

    memset(one.a,,sizeof(one.a));

    for(int i=;i<;i++)one.a[][(i%)*+i]=;

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int l,r,k;

        scanf("%d%d%d",&l,&r,&k);

        init(k);

        Matrix ansr=one*(base^(r));

        Matrix ansl=one*(base^(l-));

        LL out=ansr.a[][]-ansl.a[][];

        out=(out%mod+mod)%mod;

        printf("%lld\n",out);

    }

    return ;

}