Fibonacci Numbers

Fibonacci numbers are defined by the following formulas: (F_1 = 1), (F_2 = 1), and (F_i = F_i-1 + F_i-2).

Your task is to compute the last (k) digits of the (n)-th Fibonacci number.

Input

The input consists of a single line containing a natural number (n), where (n $\le$ 10^18), and (k = 3).

Output

The output should be a single line containing the result: the last (k) digits of the (n)-th Fibonacci number.

Examples