Три одиниці

Дуже проста

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 128 мегабайтів

Обчисліть кількість послідовностей довжини $n$ , що складаються лише з нулів та одиниць, в яких не зустрічається три одиниці поспіль.

Вхідні дані

Довжина послідовностей $n (1 \leq n \leq 1 0^{5})$ .

Вивести кількість шуканих послідовностей за модулем $12345$ .

Вхідні дані #1

Відповідь #1

Вхідні дані #2

Відповідь #2

Відправки 23K

Коефіцієнт прийняття 37%