自然数的拆分 题目描述 把自然数Ｎ（N<＝1000）分解为若干个自然数之和，求出有多少不同的分解方案？注意：交换两个数仍算是同一种方案，如3=1+23=2+1是同一种方案。

输入格式 第一行N.

输出格式 不同的分解方案数，结果对1000000000取模。

数据范围与提示 样例说明：7种方案如下：（不要输出）

5=1+4

5=1+1+3

5=1+1+1+2

5=1+1+1+1+1

5=1+2+2

5=2+3

5=5

输入输出样例 样例1 输入样例 复制 5 输出样例 复制 7

过不去超时```

#include <bits/stdc++.h>
using namespace std;
 
int q(int n,int m){
	if(n==1||m==1){
		return 1;
	}
	if(n<m)  return q(n,n);
	if(n==m){
		return q(n,m-1)+1;
	}
	if(n>m)
		return q(n,m-1)+q(n-m,m);
}
 
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		printf("%d\n",q(n,n));
	}
	return 0;
}