e-olymp
Problems

Three ones

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 (1n105).

Output

Print the required number of sequences modulo 12345.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
1
Output example #1
2
Input example #2
4
Output example #2
13