题目详情
返回题库题目描述
一个整数总可以拆分为2的幂的和。
例如：7可以拆分成
7=1+2+4,7=1+2+2+2,7=1+1+1+4,7=1+1+1+2+2,
7=1+1+1+1+1+2,7=1+1+1+1+1+1+1
共计6种不同拆分方式。
再比如：4可以拆分成：4=4,4=1+1+1+1,4=2+2,4=1+1+2
用f(n)表示n的不同拆分的种数，例如f(7)=6
要求编写程序，读入n，输出f(n)mod10^9.
输入描述
一个整数n.
输出描述
一个整数，表示f(n)mod10^9
数据范围
1≤N≤1000000