AIOC Banner

Problem: Fibonacci

Want to try solving this problem? You can submit your code online if you log in or register.


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).

Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2



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


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated: 21 September 2023, 10:56pm AEST