Вычислить количество последовательностей длины n, состоящих только из нулей и единиц, в которых не встречается три единицы подряд.

Входные данные

Длина последовательностей n (1 ≤ n ≤ 105).

Выходные данные

Вывести количество искомых последовательностей по модулю 12345.