小明装逼进行时
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
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（注意数据范围哦）
