\begin{problem}{Fib. Числа Фибоначчи 1, 2, 3 (*), 5 (*)}{fib.in}{fib.out}{2 секунды}{64 мегабайта}

Числа Фибоначчи задаются формулами $F_1 = 1$, $F_2 = 1$, 
$F_i = F_{i - 1} + F_{i - 2}$. Требуется посчитать последние $k$ цифр $n$-го
числа Фибоначчи.

\InputFile

В первой строке входного файла содержится натуральное число $n$.

\Variants
Fib1: $n \leq 10^{6}$, $k = 9$.

Fib2: $n \leq 10^{18}$, $k = 9$.

Fib3 (*): $n \leq 10^{10\,000}$, $k = 4$.

Fib5 (*): $n \leq 10^{10^7}$, $k = 3$.

\OutputFile

Первая строка выходного файла должна содержать единственно число --- ответ
на задачу.

\Example

\begin{example}
\exmp{
2
}{
1
}%
\exmp{
10
}{
55
}%
\end{example}

\end{problem}
