e-olymp
Змагання

ADA Training - October 4 - DP

Три одиниці

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

Вхідні дані

Довжина послідовностей n (1n105).

Вихідні дані

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

Ліміт часу 1 секунди
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
1
Вихідні дані #1
2
Вхідні дані #2
4
Вихідні дані #2
13