1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int md = 1e9+7;
struct node
{
ll cnt,sum,snum;
node(){
cnt=-1;
sum=0;
snum=0;}
node(ll cnt,ll sum,ll snum):cnt(cnt),sum(sum),snum(snum){}
}dp[50][8][8];
ll p[20];
int a[20];
node dfs(int pos,int remain,int sum,bool limit)
{
if(pos==-1)
{
node res;
res.cnt=(remain!=0&&sum!=0);
res.snum=0;
res.sum=0;
return res;
}
if(!limit&&dp[pos][remain][sum].cnt!=-1)return dp[pos][remain][sum];
int up = limit?a[pos]:9;
node re(0,0,0);
node r;
for(int i=0;i<=up;i++)
{
if(i==7)continue;
r=dfs(pos-1,(remain+i)%7,(sum*10+i)%7,i==up&&limit);
re.cnt+=r.cnt;
re.cnt%=md;
re.sum=(re.sum+r.sum)%md;
re.sum+=((i*p[pos])%md*r.cnt%md)%md;
re.sum%=md;
re.snum=(re.snum+r.snum)%md;
re.snum+=((r.cnt%md*(i*p[pos])%md)%md*(i*p[pos])%md+((2*i*p[pos])%md*(r.sum)%md)%md)%md;
}
return limit?re:dp[pos][remain][sum]=re;
}
ll solve(ll x)
{
node res(0,0,0);
int p = 0;
while(x)
{
a[p++]=x%10;
x/=10;
}
res = dfs(p-1,0,0,1);
return res.snum;
}
int main()
{ p[0]=1;
for(int i=1;i<20;i++)p[i]=(p[i-1]*10)%md;
int t ;
scanf("%d",&t);
while(t--)
{
ll l,r;
scanf("%lld %lld",&l,&r);
printf("%lld\n",(solve(r)%md-solve(l-1)%md+md)%md);
}
return 0;
}
|