Обчисліть кількість послідовностей довжини n, що складаються лише з нулів та одиниць, в яких не зустрічається три одиниці поспіль.
Довжина послідовностей n (1≤n≤105).
Вивести кількість шуканих послідовностей за модулем 12345.