1391 -- Library
Time Limit :1000 MS Memory Limit :65536 KB
Accepts : 135 Submits : 349
User Accepts : 93 User Submits : 101
<Submit>   <Statistics>   <Discuss>

Description

As we all know, there are very long stairs before our library in campus III of our school. It is so tired for us to go up stairs. Alpc60 has to go up and down stairs every day, what a boring walk!
One day when alpc60 went up stairs, he thought that every time he can step over one or two stairs, if there are n stairs, then how many ways he can reach the top?
The clever ACMers, can you help alpc60 to calculate how many ways he can go up n (1 <= n <= 1,000,000,000) stairs.
Because the number of the answer will be so large, you must output the number module by 9901.

Input

Each line of the input contains a number n indicating the stairs number.
Input is ended with -1 which is not the stairs number.
 

Output

For each case of the input output the possible ways module by 9901.
 

Sample Input

1
2
5
-1

Sample Output

1
2
8

Hint

The Bruce force method will simply lead to the Time Limit Exceeded error, try some efficient method to solve this problem.

 

Source

Alpc NUDT campus contest 2009
<Submit>   <Statistics>   <Discuss>
 


Powered by Zhang Zhaoning PDL College of Computer
Since 2006.03.09 | 2007.11.22 | 2010.03.02 Copyright (r) 2006 - 2010 All Rights Reserved