import java.math.BigInteger;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

	Scanner cin = new Scanner(System.in);

	int n = cin.nextInt();

	BigInteger bi = new BigInteger("0");

	for (int i = 0; i <= n; i++) {

		BigInteger temp = new BigInteger(i+"");

		temp = temp.pow(8);

		bi = bi.add(temp);

		bi = bi.mod(new BigInteger("123456789"));

	}

	System.out.println(bi.toString());

	

}

}