favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

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