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