{"trustable":false,"sections":[{"title":"题目描述","value":{"format":"HTML","content":"\u003cdiv\u003e把一个数$N$拆分成$2$的$i$次幂之和\n\u003cbr\u003e比如$N$等于$5$时:\n\u003cbr\u003e$N$\u003d\n\u003cbr\u003e$1$+$1$+$1$+$1$+$1$\n\u003cbr\u003e$1$+$1$+$1$+$2$\n\u003cbr\u003e$1$+$2$+$2$\n\u003cbr\u003e$1$+$4$\n\u003cbr\u003e共$4$种情况\n\u003cbr\u003e对于$N$ ($1$ $\u0026lt;\u003d$ $N$ $\u0026lt;\u003d$ $1,000,000$),请你计算有多少种拆分方式。 .\n\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入格式","value":{"format":"HTML","content":"\u003cdiv\u003e 一行,一个数字,N\u003c/div\u003e"}},{"title":"输出格式","value":{"format":"HTML","content":"\u003cdiv\u003e一行,一个数字,代表N的拆分方案数。由于结果可能很大,当结果足够大时输出它的最后9位\u003c/div\u003e"}},{"title":"样例输入","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e5\u003c/pre\u003e"}},{"title":"样例输出","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e4\u003c/pre\u003e"}}]}