Задачи
Три единицы
Три единицы
Вычислить количество последовательностей длины $n$, состоящих только из нулей и единиц, в которых не встречается три единицы подряд.
\InputFile
Длина последовательностей $n~(1 \le n \le 10^5)$.
\OutputFile
Вывести количество искомых последовательностей по модулю $12345$.
Входные данные #1
1
Выходные данные #1
2
Входные данные #2
4
Выходные данные #2
13