A **partition** of a positive integer *n* is a multiset of positive integers such that their sum is equal to *n*. We denote the number of partitions of n by *p(n)*. What is the number of ways to **partition** *n* into no more than *k* positive integers?

**Difficulty**: Very hard.

### Input

- There are two integers,
*n*and*k*.

### Output

Output the number of ways modulo 10^9+7 to split n into no more than *k* positive integers.

### Example

Given *n*=5 and *k*=3, there are in total 5 solutions: (1+1+3), (1+2+2), (1+4), (2+3), and (5). Thus, the correct output is 5.

### Solution: C++

```
#include<iostream>
using namespace std;
int const max_n=2000; //max value for n
int m[max_n][max_n]={0}; //memorization matrix supposing k <= n <= 2000
int mod = 1000000007;
int partition(int sum, int largestNumber){
if (largestNumber==0) //already consumed all k numbers, n can't be further partitioned
return 0;
if (sum==0) //n correctly partitioned
return 1;
if (sum<0) //n has not been correctly partitioned
return 0;
if (m[sum][largestNumber]!=0) //use memorization of previous calculated partitions
return m[sum][largestNumber];
// partitions including the largest number + partitions not including it
m[sum][largestNumber]=(partition(sum,largestNumber-1)%mod
+ partition(sum-largestNumber,largestNumber)%mod)%mod;
return m[sum][largestNumber];
}
int main(){
int n;
int k;
cin>>n;
cin>>k;
s=partition(n,k);
cout<<s;
}
```