小明装逼进行时
作业已超过截止时间,您无法递交本题目。
Background
小明是一个爱装逼的好孩纸,今天他继续他伟大光荣的装逼事业。
Description
今天小明决定做一个二人。他想知道任何一个整数n拆成2的幂次之和,有几种拆法(数字相同顺序不同算同一种)。例如n=5,共有4种方法:\(5=4+1=2+2+1=2+1+1+1=1+1+1+1+1\)。注意如果n本身是2的幂次,则n=n也算一种拆法。~~(猜猜小明今天会不会在二海中迷茫而真的变成一个二人呢?)~~
Format
Input
一个正整数n
Output
拆法总数对100000007取模
Sample 1
Input
5
Output
4
Limitation
1s, 1024KiB for each test case.
Hint
n≤1e9(注意数据范围哦)