https://www.spoj.com/problems/NUMTSN/
Please help me in above question. I am getting WA. Anyone please??
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define lld long double
#define w(x) ll x;cin>>x;while(x--)
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) __detail::__lcm(a,b)
#define goog(tno) cout << "Case #" << tno <<": "
#define PRESS_F_TO_PAY_RESPECT ios_base::sync_with_stdio(false), cin.tie(nullptr)
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define bug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define bug(x...)
#endif
ll dx[]= {-1,-1,-1,0,0,1,1,1};
ll dy[]= {-1,0,1,-1,1,-1,0,1};
const lld pi=3.1415926535897932384626433832795;
const ll INF=1e18;
const ll mod=1000000007;
const ll maxn=1e5+5;
template<typename T>
void printv(const vector<T>& v) { for(auto i:v) cout<<i<<' '; cout<<'\n'; }
template<typename T>
void printv(const vector<pair<T, T>>& v) { for(auto p:v) cout<<"("<<p.first<<","<<p.second<<"),"; cout<<'\n'; }
string a,b;
string subone(string& num){
string res = "";
bool done = 0;
for(int i = num.length() - 1; i >=0; i--){
if(num[i] != '0')
{num[i] = char(num[i] - 1);break;}
else num[i] = '9';
}
for(int i = 0; i < num.length(); i++){
res.push_back(num[i]);
}
//if(res == "")res ="0";
return res;
}
ll dp[55][2][20][20][20];
bool vis[55][2][20][20][20];
ll solve(string &s,ll idx,ll tight,ll cnt3,ll cnt6,ll cnt9){
if(idx==s.size()){
return (cnt3==cnt6&&cnt6==cnt9&&cnt3>0);
}
ll &ans=dp[idx][tight][cnt3][cnt6][cnt9];
if(vis[idx][tight][cnt3][cnt6][cnt9]) return ans;
vis[idx][tight][cnt3][cnt6][cnt9]=1;
ans=0;
if(tight){
for(ll i=0;i<=s[idx]-'0';i++){
if(i==s[idx]-'0'){
ans=(ans%mod+solve(s,idx+1,1,(i==3)+cnt3,(i==6)+cnt6,(i==9)+cnt9)%mod)%mod;
}else{
ans=(ans%mod+solve(s,idx+1,0,(i==3)+cnt3,(i==6)+cnt6,(i==9)+cnt9)%mod)%mod;
}
}
}else{
for(ll i=0;i<=9;i++){
ans=(ans%mod+solve(s,idx+1,0,(i==3)+cnt3,(i==6)+cnt6,(i==9)+cnt9)%mod)%mod;
}
}
return ans;
}
int main(){
PRESS_F_TO_PAY_RESPECT;
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
w(T){
cin>>a>>b;
a=subone(a);
memset(vis,0,sizeof vis);
ll ans1=solve(a,0,1,0,0,0);
memset(vis,0,sizeof vis);
ll ans2=solve(b,0,1,0,0,0);
cout<<(ans2-ans1+mod)%mod<<'\n';
}
return 0;
}