Fibonacci numbers

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 204

Solved: 77

Description
Fibonacci numbers is defined as below:
F[1] = 0
F[2] = 1
F[n] = F[n-1] + F[n-2]
Given an integer n ( 1 <= n <= 10^8 ), output F[n] mod 2009.

Input
The input contains several test cases.
Each case with one number n ( 1 <= n <= 10^8 ).
Output
F[n] mod 2009.
sample input
1
2
4
sample output
0
1
2
hint
source
© 2015 HUST ACMICPC TEAM. All Right Reserved.