use std::{fs::File, io::{BufWriter, Write}};

const MODULO: u64 = 666013;
// m => m * m
fn square(m: &mut [u64; 4]) {
    //
    // a b
    // c d
    //
    // (a*a + b*c)  (a*b + b*d)
    // (a*c + c*d)  (b*c + d*d)
    let aa = (m[0] * m[0]) % MODULO + (m[1] * m[2]) % MODULO;
    let bb = (m[0] * m[1]) % MODULO + (m[1] * m[3]) % MODULO;
    let cc = (m[0] * m[2]) % MODULO + (m[2] * m[3]) % MODULO;
    let dd = (m[1] * m[2]) % MODULO + (m[3] * m[3]) % MODULO;
    m[0] = aa % MODULO;
    m[1] = bb % MODULO;
    m[2] = cc % MODULO;
    m[3] = dd % MODULO;
}
// a => a * b
fn mult(a: &mut[u64; 4], b: &[u64; 4]) {
    let mut foo = [0u64; 4];
    for i in 0..2 {
        for j in 0..2 {
            for k in 0..2 {
                foo[i * 2 + j] += (a[i * 2 + k] * b[k * 2 + j]) % MODULO;
                foo[i * 2 + j] %= MODULO;
            }
        }
    }
    for i in 0..4 {
        a[i] = foo[i];
    }
}

fn main() {
    let mut writer = BufWriter::new(File::create("kfib.out").unwrap());
    let k = std::fs::read_to_string("kfib.in").unwrap().parse::<u64>().unwrap();
    if k == 0 {
        write!(writer, "0").unwrap();
        return;
    }
    if k == 1 {
        write!(writer, "0").unwrap();
        return;
    }
    let mut k = k - 1;
    let mut pow2 = [0, 1, 1, 1];
    let mut m = [1, 0, 0, 1];
    while k > 0 {
        if k % 2 == 1 {
            mult(&mut m, &pow2);
        }
        square(&mut pow2);
        k /= 2;
    }
    write!(writer, "{}", m[3]).unwrap();
}