Product sum

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1000000007;
ll st[20][20];
ll calculate(ll z)
{
    int g,h,d,nt=0;
    ll re=0,x=z;
    vector<int>dg;
    while(x){
        nt++;
        dg.push_back(x%10);
        x/=10;
    }
    for(g=nt;g>0;g--){
        d=dg[g-1];
        if(g==nt||g==1)x=st[g-1][d];
        else x=st[g-1][d]-st[g-1][0];
        for(h=g;h<nt;h++){
            x*=dg[h];
            x%=M;
        }
        re+=x;
        re%=M;
    }
    return re;
}
int main()
{
    int g,h,t,s=1;
    ll q,w,re;
    st[0][0]=0;
    for(g=1;g<=9;g++)
        st[0][g]=st[0][g-1]+g;
    st[0][10]=45;
    for(g=1;g<=18;g++){
        st[g][0]=st[g-1][10];
        for(h=1;h<=10;h++){
            st[g][h]=((st[g][0]*(h-1))%M+st[g][h-1]-(st[g-1][0]*(h-1))%M)%M;
            if(st[g][h]<0)st[g][h]+=M;
        }
    }
    scanf("%d",&t);
    while(t--){
        scanf("%lld %lld",&q,&w);
        re=calculate(w)-calculate(q-1);
        if(re<0)re+=M;
        printf("Case %d: %lld\n",s++,re);
    }
    return 0;
}