SPOJ — NUMTSN — 369 Numbers

,
1

I am trying to solve this problem SPOJ.com - Problem NUMTSN on spoj. I tried to use dynamic programming. I am getting WA. Here is my code

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
long long  DP[51][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;
}
2

long long ans=solve1(b)-solve1(a);

This may lead to negative number since we are doing mod inside the function. So in main do ans = ans+mod and then ans%=mod; and then return ans;