#### Getting a TLE but can’t debug it

Description

A sequence is called good if each number is divisible by the next number in the sequence. You have to find the number of good sequences with length K containing positive integers ≤ N.

Since the answer can be large, print it 109 + 7.

Input Format

The first line of the input contains one integer T – the number of test cases. Then T test cases follow.

The first and only line of each test case contains two space-separated integers N, K.

Output Format

For each test case, print the number of good sequences with length K containing positive integers ≤ N. Since the answer can be large, print it 109 + 7.

Constraints

1≤ T ≤ 400000

1≤ N, K ≤ 2000

``````#include<bits/stdc++.h>
using namespace std;
#define int long long

int n,k;
int mod=1000000007;
int dp[2500][2500],sum1[2500][2500];
vector<vector<int>> fact(2500);

void factors(){
for(int i=1;i<2500;i++){
for(int j=1;j*j<=i;j++){
if(i%j==0){
if(j*j==i){
fact[i].push_back(j);
}
else {
fact[i].push_back(j);
fact[i].push_back(i/j);
}
}
}
}
}

int rec(int max_no,int len){
if(len==1) return dp[max_no][len]=1;
if(dp[max_no][len]!=-1){
return dp[max_no][len];
}
int sum=0;
for(auto i:fact[max_no]){
sum=(sum+rec(i,len-1))%mod;
}
return dp[max_no][len]=sum;
}

int rec1(int max_no,int len){
if(max_no==1) return rec(max_no,len);
if(sum1[max_no][len]!=-1) return sum1[max_no][len];
return sum1[max_no][len]=(rec1(max_no-1,len)+rec(max_no,len))%mod;
}

void solve(){
cin>>n>>k;
int sum=0;
for(int i=1;i<=n;i++){
sum=(sum+rec(i,k))%mod;
}
cout<<rec1(n,k)<<"n";

}

signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
factors();
for(int i=0;i<2500;i++){
for(int j=0;j<2500;j++){
dp[i][j]=-1;
sum1[i][j]=-1;
}
}
int t;cin>>t;while(t--)
solve();

}

``````

I am getting a TLE . But don’t know why?
How can I optimize my code?

Source: Windows Questions C++