\begin{problem}{Ones. Три единицы}{ones.in}{ones.out}{2 секунды}

Требуется найти количество последовательностей заданной длины из нулей и единиц, 
таких что в них не встречается трех единиц подряд. 


\InputFile

Входной файл содержит одно натуральное число $n$ --- длину последовательностей 
($n \le 10^9$).

\OutputFile        

В выходной файл выведите количество последовательностей по модулю $12\,345$.

\Example

\begin{example}
\exmp{
1
}{
2
}%
\exmp{
4
}{
13
}%
\end{example}

\end{problem}
