单身!
依然单身！
吉哥依然单身！
DS级码农吉哥依然单身！
所以，他生平最恨情人节，不管是214还是77，他都讨厌！
吉哥观察了214和77这两个数，发现：
2+1+4=7
7+7=72
77=711
最终，他发现原来这一切归根到底都是因为和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
不能出现7的,平方和比较麻烦，要把他按平方公式拆开计算
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iomanip>
#include<cmath>
#include<float.h>
#include<string.h>
#include<algorithm>
#define sf scanf
#define pf printf
#define sca(x) scanf("%d",&x)
#define mm(x,b) memset((x),(b),sizeof(x))
#include<vector>
#include<queue>
#include<map>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
typedef long long ll;
const ll mod=1e9+7;
const double eps=1e-8;
using namespace std;
const double pi=acos(-1.0);
const int inf=0xfffffff;
const int N=1000005;
struct node
{
ll cnt;//ÊýµÄ¸öÊý
ll sum;//¸÷ÊýÖ®ºÍ
ll ssum;//Âú×ãÌõ¼þµÄÊýƽ·½Ö®ºÍ
node(int a=-1,int b=0,int c=0) { cnt=a;sum=b;ssum=b; }//³õʼ»¯
}dp[25][12][12];
ll p[25];
int num[25];
void first()
{
p[0]=1;
rep(i,1,21)
p[i]=(p[i-1]*10)%mod;
}
node dfs(ll pos,ll sum,ll ssum,ll limit)//λÊý£¬Î»ÊýºÍ%7£¬ÊýÖµ%7£¬ÊÇ·ñÊÇÉÏÏÞ
{
node ans;
ans.cnt=0;
if(pos==0)
{
if(limit=1&&sum!=0&&ssum!=0)
ans.cnt=1;
return ans;
}
if(!limit&&dp[pos][sum][ssum].cnt!=-1) return dp[pos][sum][ssum];
int up=limit?num[pos]:9;
for(int i=0;i<=up;i++){
if(i==7)continue;
node next=dfs(pos-1,(i+sum)%7,(ssum*10+i)%7,limit&&(i==up) );
ans.cnt+=next.cnt;
ans.cnt%=mod;
ans.sum+=(next.cnt*i%mod*p[pos-1 ]%mod+next.sum )%mod;
ans.sum%=mod;
ans.ssum+=(next.ssum+2*(p[pos-1]*next.sum%mod*i)%mod )%mod;
ans.ssum%=mod;
ans.ssum+=(p[pos-1]*p[pos-1]%mod*next.cnt%mod*i*i)%mod;
ans.ssum%=mod;
}
if(!limit)
dp[pos][sum][ssum]=ans;
return ans;
}
ll solve(ll n)
{
int pos=0;
ll x=n;
while(x)
{
num[++pos]=x%10;
x/=10;
}
//mm(dp,-1);
node ans=dfs(pos,0,0,1);
return ans.ssum;
}
int main()
{
first();ll l,r;
int re;
sf("%d",&re);
while(re--)
{
sf("%lld%lld",&l,&r);
pf("%lld\n",((solve(r)-solve(l-1))%mod+mod)%mod);
}
return 0;
}
