import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
static int MAX = 100010;
static int f[] = new int[MAX];
{
Scanner in
= new Scanner
(System.
in); int n = in.nextInt();
f[1] = 2;
f[2] = 4;
f[3] = 7;
for(int i = 4; i <= n; i++) {
f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;
}
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBJZGVvbmUKewoJc3RhdGljIGludCBNQVggPSAxMDAwMTA7CglzdGF0aWMgaW50IGZbXSA9IG5ldyBpbnRbTUFYXTsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCVNjYW5uZXIgaW4gPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwoJCWludCBuID0gaW4ubmV4dEludCgpOwoJCWZbMV0gPSAyOyAKCQlmWzJdID0gNDsgCgkJZlszXSA9IDc7CgkJZm9yKGludCBpID0gNDsgaSA8PSBuOyBpKyspIHsKCQkJZltpXSA9IChmW2ktMV0gKyBmW2ktMl0gKyBmW2ktM10pICUgMTIzNDU7CgkJfQoJCVN5c3RlbS5vdXQucHJpbnRsbihmW25dKTsKCX0KfQo=