页面无法加载？点击这里可能会修复。
Placeholder

#1093
子任务

Sumsets 2 1s 64MB

问题

임의의 숫자 N이 주어졌을 때 2의 제곱수들의 합이 N이 되는 경우가 총 몇 가지가 있는지 알아내는 프로그램을 작성하라.

 

예를 들어 N = 7일 경우는 다음과 같이 6 가지가 존재한다. 

1. 1+1+1+1+1+1+1 

2. 1+1+1+1+1+2 

3. 1+1+1+2+2 

4. 1+1+1+4 

5. 1+2+2+2 

6. 1+2+4​ 


输入

첫 번째 줄에 정수 N 이 입력된다. (1 \le N \le 1,000,000)


输出

첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,007으로 나눈 나머지를 출력한다.


子任务

编号 分数 条件
#120分

N \le 10

#240分

N \le 100

#340分

추가 제약 조건 없음


示例 #1

1
1

示例 #2

7
6


来源

USACO January 2005 Silver 1번

需要登录才能编写代码。