将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。

 

Input输入1个数N(1 <= N <= 50000)。Output输出划分的数量Mod 10^9 + 7。Sample Input

6

Sample Output

4

 每个数最多分成sqrt(n*2)个不一样的数,比如10分成1,2,3,4,其实就是(1 + 4) / 2 *4 = 10,max(j) = sqrt(n*2).把i分成j个数有两个来源途径1.i - j分成j个数,每个数+1,i - j分成j - 1个数+j.

code:

#include 
      
       #include 
       
        #include 
        
         #define mod 1000000007using namespace std;long long dp[50010][320];int main(){    int n;    cin>>n;    dp[0][0] = 1;    for(int i = 1;i <= n;i ++)    {        for(int j = 1;j <= sqrt(i * 2);j ++)        {            dp[i][j] = (dp[i - j][j - 1] + dp[i - j][j]) % mod;        }    }    long long ans = 0;    for(int i = 1;i <= sqrt(n * 2);i ++)    {        ans = (ans + dp[n][i]) % mod;    }    cout<