Integer partition

take N The sum of several different integers , How many different ways are there , for example ：n = 6,{6} {1,5} {2,4} {1,2,3}, common 4 Kind of . Because of the big data , Output Mod 10^9 + 7 As a result of .

Input

Input 1 Number N(1 <= N <= 50000).

Output

Output the number of partitions Mod 10^9 + 7.

Sample Input

6

Sample Output

4

The question ： Give a number n, seek n Can be divided into several sets , Make the sum of the numbers in each set equal to n.

Ideas ： This question is in Chinese dp do ,dp【i】【j】 It means that you will i It is divided into j Add up the numbers . When  i be equal to 9,j be equal to 3 when ,dp【i-j】【j】 namely dp【6】【3】 be equal to 1, because 6 Can be divided into 1,2,3 A kind of ,dp【i-j】【j-1】 namely dp【6】【2】 Can be divided into （1,5） and （2,4） Two and dp【9】【3】 Exactly equal to 3, all dp【i】【j】=dp【i-j】【j】+dp【i-j】【j-1】. After the state transition equation is written, you need to know the numbers n It can be divided into sart（2*n） Add bits . then for Add one cycle after another , The code is as follows ：

#include<stdio.h>
#include<math.h>
int a[50010][350];
int main()
{
    int n,i,j,k;
    while(~scanf("%d",&n))
    {
        a[0][0]=1;
        int sum=0;
        k=sqrt(2*n);
        for(i=1;i<=n;i++)
        {
             for(j=1;j<=k;j++)
             {
                if(i>=j)
                a[i][j]=(a[i-j][j]+a[i-j][j-1])%1000000007;
             }
        }
        for(i=1;i<=k;i++)
            sum=(sum+a[n][i])%1000000007;
        printf("%d\n",sum);
    }
    return 0;
}