Problem: Fibonacci

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

Fibonacci

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.

Input

The input will contain one line with one integer N (1 <= N <= 30,000,000) followed by a new line.

Output

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

Scoring

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