整数的特殊划分

★问题描述： 给定一个正整数N，将其分解为若干个整数的和，且这些整数都是2的 k 次方(k>=0)， 请问共有多少种分解方法？ 例如，对于整数5，有 5=1+1+1+1+1； 5=1+1+1+2； 5=1+2+2； 5=1+4 共4种分解方法。 对于整数8，有 8=1+1+1+1+1+1+1+1； 8=1+1+1+1+1+1+2； 8=1+1+1+1+2+2； 8=1+1+2+2+2; 8=2+2+2+2; 8=1+1+1+1+4; 8=1+1+2+4; 8=2+2+4; 8=4+4; 8=8 共10种分解方法。 输入格式 每组输入数据仅包含一个整数 N (1 <= N <= 10000)。 注意:这里原来题目是1 <= N <= 100000,现在改为:1 <= N <= 10000 输出格式 输出一个整数M。M为分解方法数，由于M可能很大，请输出 M00000000。 输入样例 5 输出样例 4