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 *N*th Fibonacci number, where
1 <= *N* <= 30,000,000.
That is, output the remainder when the *N*th 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 *N*th Fibonacci number modulus 1000
(the remainder when divided by 1000).

4

3

17

597

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-2021

Page generated: 21 October 2021, 7:56pm AEDT