This is an editorial post of the code forces problem Mashmokh and ACM.

Table of Contents

## Problem Statement

Mashmokh’s boss, Bimokh, didn’t like Mashmokh. So he fired him. Mashmokh decided to go to university and participate in ACM instead of finding a new job. He wants to become a member of Bamokh’s team. In order to join he was given some programming tasks and one week to solve them. Mashmokh is not a very experienced programmer. Actually he is not a programmer at all. So he wasn’t able to solve them. That’s why he asked you to help him with these tasks. One of these tasks is the following.

A sequence of *l* integers *b*_{1}, *b*_{2}, …, *b*_{l} (1 ≤ *b*_{1} ≤ *b*_{2} ≤ … ≤ *b*_{l} ≤ *n*) is called good if each number divides (without a remainder) by the next number in the sequence. More formally for all *i* (1 ≤ *i* ≤ *l* - 1).

Given *n* and *k* find the number of good sequences of length *k*. As the answer can be rather large print it modulo 1000000007 (10^{9} + 7).

## Input

The first line of input contains two space-separated integers *n*, *k* (1 ≤ *n*, *k* ≤ 2000).

## Output

a single integer — the number of good sequences of length *k* modulo 1000000007 (10^{9} + 7).ExamplesInputCopy

3 2

Output

5

**Detailed Editorial**

In the above problem, we have to find a number of **k** length good sequence from the array consisting of **n** integers (1, 2, …, n).

As per definition, **a good sequence is a sequence where b(i+1)|b(i) for all (1 ≤ I ≤ l-1),** where l is the length of the sequence.

The idea is that we will iterate the array (1, 2, .., n) from backward and check whether for element **b(i-1)** is a factor of **b(i)**.

For example, in sequence [1,2,3], we will traverse from backward and check whether 2 is a factor of 3 or not.

For checking factors we can run an O(√n) loop to find it but finding factors for each element of the array will be too costly and will give **TLE**.

So, for resolving TLE, we will pre-compute the factors before, since constraints of n are **(1 ≤ n ≤ 2000), **we can afford pre-computing the factors before.

Later will recursively find** k length good subsequence for every element of the array.If we find a good sequence of length k, we will return 1 and we will continue it for every subsequence.It will be a recursive solution which will be changed to memoized version of DP to pass all the given test under constraints. Also, don’t forget to represent your answer in modulo (1e9+7).That’s it, hope the idea is clear. If you have any doubts ask it in the **comment section.

**Detailed Solution in C++**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define mod 1000000007
ll dp[2001][2001];
map<ll, set<ll>> mp;
ll F(ll n, ll k)
{
if(k == 1 || n == 1) return 1;
if(dp[n][k] != -1) return dp[n][k];
ll ans =((F(n, k-1) % mod) + (F(1, k-1) % mod) % mod);
for(auto i = mp[n].begin(); i != mp[n].end(); i++)
{
ll s = 0, x = *i;
if(n % x == 0 && x == n/x)
{
s = (F(x, k-1)) % mod;
}
else if(n % x == 0)
{
s = (F(x, k-1) % mod) + (F(n/x, k-1) % mod) % mod;
}
ans = ((ans % mod) + (s % mod) % mod);
}
return dp[n][k] = ans % mod;
}
int32_t main()
{
ll t = 1;
while(t--)
{
ll n, k;
cin >> n >> k;
for(ll i = 2; i <= 2000; i++)
{
for(ll j = 2; j <= sqrt(i); j++)
{
if (i % j == 0)
{
mp[i].insert(j);
}
}
}
memset(dp, -1, sizeof(dp));
ll s = 0;
for(ll i = n; i >= 1; i--)
{
s = (s % mod + F(i, k) % mod) % mod;
}
cout<<(s % mod)<<"\n";
}
return 0;
}
```

Practice one more DP problem