Three ones

Find the number of sequences of length $n$, consisting only of zeros and ones, that do not have three one's in a row.

Input

The length of the sequences $n(1\le n\le 10^5)$.

Output

Print the required number of sequences modulo $12345$.

Examples