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

Вхідні дані

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

Вихідні дані

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