import java.util.Scanner;

public class Main {
    // 主函数
    public static void main(String[] args) {
        // 读取输入的整数
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        // 计算结果
        long result = 0;
        for (int i = 1; i <= n; i++) {
            result += pow(i, 8); // 调用自定义幂函数并累加结果
            result %= 123456789; // 取模操作
        }

        // 输出结果
        System.out.println(result); // 打印最终结果
    }

    // 自定义幂函数
    public static long pow(long base, long exponent) {
        long result = 1;
        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result = (result * base) % 123456789; // 计算幂的过程中取模
            }
            base = (base * base) % 123456789; // 计算幂的过程中取模
            exponent >>= 1; // 右移一位，相当于除以2
        }
        return result;
    }
}