페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#1948

목재 쌓기 1s 256MB

문제

목재를 운반하기 위해 쌓아야 한다. 

옆에서 봤을 때 목재를 쌓은 모양은 아래와 같다.

 

목재는 여러 층으로 쌓인다. 당연히 위에 층은 아래 층보다 통나무의 수가 적어야 한다. 

그리고 각 층의 목재들은 연속적으로 놓여야 한다.

맨 아래 줄에 놓인 목재의 수가 주어졌을 때, 목재를 쌓아 두는 방법이 얼마나 많은 지 출력하라.


입력

통나무 수 n (1≤n≤2,000,000,000)가 주어진다.


출력

각 케이스마다 방법의 수를 105으로 나눈 나머지를 출력한다.


예제 #1

2
2

예제 #2

3
34
로그인해야 코드를 작성할 수 있어요.