小明装逼进行时

小明装逼进行时

作业已超过截止时间,您无法递交本题目。

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(注意数据范围哦)

熟悉网站

未认领
状态
已结束
题目
3
开始时间
2021-07-01 00:00
截止时间
2024-06-30 23:59
可延期
24.0 小时