Q:

Count numbers in a range where count of 3s=count of 6s=count of 9s

Here is the problem description 
A number is said to be a 369 number if
1-The count of 3s is equal to count of 6s and the count of 6s is equal to count of 9s.
2-The count of 3s is at least 1.
For Example 12369, 383676989, 396 all are 369 numbers whereas 213, 342143, 111 are not.
Given A and B find how many 369 numbers are there in the interval [A, B]. Print the answer modulo 1000000007.
Constraints
T<=100
1<=A<=B<=10^50
Here is my code 
    #include <bits/stdc++.h>
    using namespace std;
    #define MOD 1000000007
    long long  DP[52][18][18][18][2];
     char  a[100],b[100];
     long long t;
     string num;
    long long  solve(long long  pos,long long cn3,long long cn6,long long cn9,long long  f)
    {
        if(cn3>=18||cn6>=18||cn9>=18)
            return 0;
        if(pos==(int)num.size())
        {
            if(cn3==cn6&&cn6==cn9&&cn3>=1)
                return 1;
        return 0;
        }

        if (DP[pos][cn3][cn6][cn9][f]!=-1) 
            return DP[pos][cn3][cn6][cn9][f]%MOD;
        long long  res=0;
        long long lmt;
        if(f==0)
            lmt=num[pos]-'0';
        else lmt=9;
        for(int dgt=0;dgt<=lmt;dgt++)
        {
            int nf=f;
            if(f==0 && dgt<lmt) nf=1;
             res+=(solve(pos+1,(dgt == 3) + cn3, (dgt == 6) + cn6, (dgt == 9) + cn9,nf)%MOD);
            res%=MOD;
        }

        return DP[pos][cn3][cn6][cn9][f]=res;

    }
    long long int solve1(string x)
    {
        num=x;
        memset(DP,-1,sizeof(DP));
        long long int result=solve(0,0,0,0,0);
        return result;
    }
        int main()
        {

            cin>>t;

            while(t--)
            {
    cin>>a>>b;
                long long ans=solve1(b)-solve1(a);
                  int sz = strlen(a), c3 = 0, c6 = 0, c9 = 0;
  for(int i = 0; i < sz; i++){
      if(a[i] == '3') c3++;
      if(a[i] == '6') c6++;
      if(a[i] == '9') c9++;
  }
  if(c3 == c6 and c6 == c9 and c3 != 0) 
      ans++;
        cout<<(ans)%MOD<<"\n";
            }
    return 0;
    } 

It is giving wrong answer although I checked it with right code it is giving same answer for common test cases.
The approach which I used was digit dp. Here is the link for that https://codeforces.com/blog/entry/53960

A:

The reason for wrong answer is that solve(b)-solve(a) can be negative and I was not adding MOD to the ans variable 

