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

Dynamic Programming - Linear

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