import java.math.BigInteger;

public class Euler909 {

    static BigInteger T(BigInteger n) {
        return n.multiply(n.add(BigInteger.ONE));
    }

    static BigInteger H(BigInteger n) {
        BigInteger m = n.multiply(n).multiply(n.add(BigInteger.ONE));
        return m.multiply(m.add(BigInteger.ONE));
    }

    static BigInteger U(BigInteger n) {
        BigInteger h = H(n);
        return h.multiply(h.add(BigInteger.ONE));
    }

    public static String solve() {
        BigInteger n = U(BigInteger.ONE);
        BigInteger value = U(n);
        long answer = value.remainder(BigInteger.valueOf(1000000000L)).longValue();
        return Long.toString(answer);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}