Input File: fibin.txt
Output File: fibout.txt
Time Limit: 1 second
Memory Limit: 64 MB
The Fibonacci sequence is defined as each number being the sum of the two previous numbers in the sequence. Thus, the first six numbers in the sequence are 1, 1, 2, 3, 5, 8.
Find the last three digits of the Nth Fibonacci number, where 1 <= N <= 30,000,000. That is, output the remainder when the Nth Fibonacci number is divided by 1000.
The input will contain one line with one integer N (1 <= N <= 30,000,000) followed by a new line.
You must output one line containing one integer M (0 <= M < 1000) — the result of the Nth Fibonacci number modulus 1000 (the remainder when divided by 1000).
The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.
For 30% of the test cases, N <= 25
For 70% of the test cases (including the 30% mentioned above), N <= 1,000,000