Fibonacci Number 3

The Fibonacci sequence starts with 0 and 1. The 0th Fibonacci number is 0, and the 1st Fibonacci number is 1. From the 2nd number onward, each number is the sum of the two previous Fibonacci numbers.

For n ≥ 2, this can be written as F_n = F_{n-1} + F_{n-2}.

Up to n=17, the Fibonacci numbers are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

Given n, write a program that finds the nth Fibonacci number.

The first line contains a natural number n. n is at most 1,000,000,000,000,000,000.

Print the remainder when the nth Fibonacci number is divided by 1,000,000.