MOD = 12345678
 
def extended_gcd(a, b):
    if b == 0:
        return (1, 0)
    x1, y1 = extended_gcd(b, a % b)
    x, y = y1, x1 - (a // b) * y1
    return (x, y)
 
def modinv(a, mod):
    x, y = extended_gcd(a, mod)
    return (x % mod + mod) % mod
 
def catalan(n):
    if n < 2:
        return 1
    n -= 2  # we want C_{n-2}
    num = 1
    den = 1
 
    for i in range(1, n + 1):
        num = num * (2 * n - i + 1) % MOD
        den = den * i % MOD
 
    catalan_n = num * modinv(den, MOD) % MOD
    catalan_n = catalan_n * modinv(n + 1, MOD) % MOD
    return catalan_n
 
# Example:
n = int(input("Nhập n (n nhỏ hơn khoảng 10^6): "))
print("Catalan(n-2) mod 12345678 =", catalan(n))
 

TU9EID0gMTIzNDU2NzgKCmRlZiBleHRlbmRlZF9nY2QoYSwgYik6CiAgICBpZiBiID09IDA6CiAgICAgICAgcmV0dXJuICgxLCAwKQogICAgeDEsIHkxID0gZXh0ZW5kZWRfZ2NkKGIsIGEgJSBiKQogICAgeCwgeSA9IHkxLCB4MSAtIChhIC8vIGIpICogeTEKICAgIHJldHVybiAoeCwgeSkKCmRlZiBtb2RpbnYoYSwgbW9kKToKICAgIHgsIHkgPSBleHRlbmRlZF9nY2QoYSwgbW9kKQogICAgcmV0dXJuICh4ICUgbW9kICsgbW9kKSAlIG1vZAoKZGVmIGNhdGFsYW4obik6CiAgICBpZiBuIDwgMjoKICAgICAgICByZXR1cm4gMQogICAgbiAtPSAyICAjIHdlIHdhbnQgQ197bi0yfQogICAgbnVtID0gMQogICAgZGVuID0gMQoKICAgIGZvciBpIGluIHJhbmdlKDEsIG4gKyAxKToKICAgICAgICBudW0gPSBudW0gKiAoMiAqIG4gLSBpICsgMSkgJSBNT0QKICAgICAgICBkZW4gPSBkZW4gKiBpICUgTU9ECgogICAgY2F0YWxhbl9uID0gbnVtICogbW9kaW52KGRlbiwgTU9EKSAlIE1PRAogICAgY2F0YWxhbl9uID0gY2F0YWxhbl9uICogbW9kaW52KG4gKyAxLCBNT0QpICUgTU9ECiAgICByZXR1cm4gY2F0YWxhbl9uCgojIEV4YW1wbGU6Cm4gPSBpbnQoaW5wdXQoIk5o4bqtcCBuIChuIG5o4buPIGjGoW4ga2hv4bqjbmcgMTBeNik6ICIpKQpwcmludCgiQ2F0YWxhbihuLTIpIG1vZCAxMjM0NTY3OCA9IiwgY2F0YWxhbihuKSkK

NA==

4