# Integer Partition

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;
}
```