Tilling problem 2 getting error in code

#1

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000009
#define ll long long

ll f(ll n,ll m)
{
if(n<=m)
{
return 1;
}
ll ans=0,p,q;
p=f(n-1,m);
q=f(n-m,m);
ans=((p%mod) + (q%mod))%mod;
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin>>t;
while(t–)
{
ll n,m;
cin>>n>>m;
ll ans=0;
ans=f(n,m);
cout<<ans%mod<<endl;
}
return 0;
}

#2

Some issues in your code:

  1. Use DP(memoization) else you will get TLE.
  2. if(n<m) return 1;
    if(n==m) return 2;// you are returning 1 which is wrong.

here check that n-m>0 because q will be 0 then