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