use std::fs::File;
use std::io::{BufRead, BufReader, Write};
use std::path::Path;

const MOD: u64 = 666_013;

#[derive(Clone, Copy)]
struct Matrix {
    a: [[u64; 2]; 2],
}

impl Matrix {
    fn new(a00: u64, a01: u64, a10: u64, a11: u64) -> Self {
        Matrix {
            a: [[a00 % MOD, a01 % MOD],
                [a10 % MOD, a11 % MOD]],
        }
    }

    fn identity() -> Self {
        Matrix::new(1, 0, 0, 1)
    }

    fn multiply(&self, other: &Matrix) -> Self {
        let mut result = Matrix::new(0, 0, 0, 0);
        for i in 0..2 {
            for j in 0..2 {
                for k in 0..2 {
                    result.a[i][j] = (result.a[i][j] + self.a[i][k] * other.a[k][j]) % MOD;
                }
            }
        }
        result
    }

    fn power(&self, mut exp: u64) -> Self {
        let mut result = Matrix::identity();
        let mut base = *self;

        while exp > 0 {
            if exp % 2 == 1 {
                result = result.multiply(&base);
            }
            base = base.multiply(&base);
            exp /= 2;
        }

        result
    }
}

fn fibonacci(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    let fib_matrix = Matrix::new(1, 1, 1, 0);
    let result = fib_matrix.power(n - 1);
    result.a[0][0]
}

fn main() {
    let path_input = Path::new("kfib.in");
    let path_output = Path::new("kfib.out");
    let input = File::open(path_input).expect("Error while opening kfib.in");
    let reader = BufReader::new(input);

    let mut k = 0;
    for line in reader.lines() {
        let line = line.expect("Error while reading");
        k = line.trim().parse::<u64>().expect("Could not convert n");
        break;
    }

    let result = fibonacci(k);
    let mut output = File::create(path_output).expect("Error while creating nr2.out");
    writeln!(output, "{}", result).expect("Error while writing output");
    
}