Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KTUAN - Phân tích số

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/ktuan


Hãy đếm số cách phân tích số N ( N<=100000 ) thành tổng các số nguyên dương.
Lưu ý 2 cách chỉ khác nhau về thứ tự các số hạng được coi là giống nhau. Ví dụ 4 có 5 cách phân tích sau:
4 = 1 + 1 + 1 + 1
4 = 1 + 1 + 2
4 = 1 + 3
4 = 2 + 2
4 = 4

Hai cách phân tích 4 = 1 + 3 = 3 + 1 chỉ được tính một lần.
Vì kết quả sẽ rất lớn nên các bạn chỉ cần đưa ra phần dư của phép chia số cách tìm được cho 1000000000 ( 10^9 ).

Input

Một số tự nhiên N duy nhất.

Output

In ra phần dư của của số cách tìm được cho 10^9.

Example

Input:
4

Output:
5

Được gửi lên bởi:VOJ problem setters
Ngày:2007-10-31
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED
Nguồn bài:Được add lên bởi Khúc Anh Tuấn

hide comments
2019-02-23 02:57:08
Ban đầu mình nghĩ là QHĐ, Tuy nhiên...cách làm này không khả quan. Mong mọi người gợi ý giải thuật.
2017-01-20 19:07:21
ac đc rồi hay lắm đm :)
2016-10-26 17:46:37 Anh Duc Le
Hình như là có test n=0 @@
2015-09-08 14:22:09
https://thewizard6296.wordpress.com/2015/09/04/5/
2015-08-18 13:42:54 Sơn Tùng M-TP
N=10^5 sao quy hoach dong? :(((
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.