頁面無法載入？點擊這裡可能會修復。
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번

需要登入才能撰寫程式碼。