Farmer John yêu cầu bò tìm các tập số khác nhau có tổng bằng số đã cho. Chỉ dùng lũy thừa nguyên của 2. Đây là các tập có tổng 7:

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

Giúp FJ đếm mọi cách biểu diễn số nguyên $N$ ($1 \le N \le 1{,}000{,}000$).

Dữ liệu vào

Một dòng chứa một số nguyên $N$.

Dữ liệu ra

Số cách biểu diễn $N$ thành tổng như trên. Có thể rất lớn nên chỉ in 9 chữ số cuối trong biểu diễn thập phân.

Ví dụ

Dữ liệu vào 1

7

Dữ liệu ra 1

6

Bài 1: Các cách biểu diễn tổng