单身! 
　　依然单身！ 
　　吉哥依然单身！ 
　　DS级码农吉哥依然单身！ 
　　所以，他生平最恨情人节，不管是214还是77，他都讨厌！ 
　　 
　　吉哥观察了214和77这两个数，发现： 
　　2+1+4=7 
　　7+7=7*2 
　　77=7*11 
　　最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！ 

　　什么样的数和7有关呢？ 

　　如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 
　　1、整数中某一位是7； 
　　2、整数的每一位加起来的和是7的整数倍； 
　　3、这个整数是7的整数倍； 

　　现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。 

Input

输入数据的第一行是case数T(1 <= T <= 50)，然后接下来的T行表示T个case;每个case在一行内包含两个正整数L, R(1 <= L <= R <= 10^18)。 

Output

请计算[L,R]中和7无关的数字的平方和，并将结果对10^9 + 7 求模后输出。

Sample Input

3
1 9
10 11
17 17

Sample Output

236
221
0

 题解：

如果我们知道了123和是和7无关的数，那么在123之前加一个1，1123也是与7无关 的数，那么如和求加上一位之后总的平方和呢，

假设我们已经知道了所有的满足条件的三位数的个数cnt和平方和ss，那么再加一位，意味着一共加了cnt*1000，

比如那132来说，那么加一位的平方就是1123^2=（1000+123）^2=1000^2 + 2*1000*abc + abc*abc;

从这个式子就能看出来，我们需要保存的数据有   满足条件的数的个数，和，以及平方和。

 

设temp为子状态

那么当前的ans的三个数据是   ：

                                  1、cnt+=temp.cnt;

                                  2、s  += temp.s + ( i * pow(10, pos) *temp.cnt);

                                  3、ss+= temp.ss+(2 * i * pow(10, pos) * temp.s) + i * pow(10, pos) * i * pow(10,pos);

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const double PI=acos(-1);
const ll mod=1e9+7;
int a[30];
struct node
{
    ll cnt;
    ll s;
    ll ss;
    node(){}
    node(ll a,ll b,ll c):cnt(a),s(b),ss(c){}
}dp[20][10][10];
ll p[30];
node dfs(ll pos,ll sta,ll sta1,int limit)
{
    if(pos<0)
    {
        if(sta&&sta1)return node(1,0,0);
        else return node(0,0,0);
    }
    if(!limit&&dp[pos][sta][sta1].cnt!=-1)return dp[pos][sta][sta1];
    ll up=limit?a[pos]:9;
    node tmp;
    ll cnt=0,s=0,ss=0;
    for(ll i=0;i<=up;i++)
    {
        if(i == 7)continue;
        tmp = dfs(pos - 1,(sta + i) % 7, (sta1 * 10 + i) % 7, limit && i == up);
        cnt = ( cnt+ tmp.cnt) % mod;
        s   = ( s  + tmp.s + (i * p[pos] % mod ) * tmp.cnt % mod ) % mod; 
        ss  = ( ss + tmp.ss+ ( (2 * i * p[pos] % mod )%mod) * tmp.s % mod + ( p[pos] % mod * p[pos] % mod * tmp.cnt) % mod * i * i % mod) % mod;
    }
    if(!limit) dp[pos][sta][sta1]=node(cnt,s,ss);
    return node(cnt,s,ss);
}
ll solve(ll x)
{
    int t=0;
    while(x)
    {
        a[t++]=x%10;
        x/=10;
    }
    return dfs(t-1,0,0,1).ss;
}
int main()
{
    int T;p[0]=1;
    for(int i=1;i<20;i++) 
        p[i]=(p[i-1]*10)%mod; 
    memset(dp,-1,sizeof(dp));
    cin>>T;
    while(T--)
    {
        ll l,r;
        cin>>l>>r;
        printf("%lld\n",(solve(r)-solve(l-1)+mod)%mod);
    }
    return 0;
}