gistfile1.java

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Main {
  BufferedReader in;
	PrintWriter out;
	StringTokenizer st;

	// TODO turn off
	static final boolean DEBUG = true;

	int n;
	int []primes;
  boolean []p;
	long[][] dp;

	void primes() {
		p= new boolean[n + 1];
		Arrays.fill(p, true);
		p[0] = false;
		p[1] = false;
    int total = 0;
		for (int i = 2; i <= n; ++i)
			if (p[i]) {
        ++total;
				if (i * 1L * i <= n)
					for (int j = i * i; j <= n; j += i)
						p[j] = false;
      }
    this.primes = new int[total];
    int idx = 0;
		for (int i = 2; i <= n; i++)
			if (p[i])
				this.primes[idx++] = i;
	}

	long rec(int n, int cnt) {
    if (cnt == 1) {
      return p[n] ? 1 : 0;
    }
		long ret = dp[cnt][n];
		if (ret == -1) {
			ret = 0;
			for (int p : primes)
				if (p <= n)
					ret += rec(n - p, cnt - 1);
				else
					break;
			dp[cnt][n] = ret;
		}
		return ret;
	}

	void solve() throws IOException {
    Timer timer = new Timer();
    timer.start();
		n = ni();
		primes();
		dp = new long[5][n + 1];
		for (int i = 0; i <= 4; i++)
			Arrays.fill(dp[i], -1L);
		long ans = rec(n, 4);
		out.println(ans);
    timer.print();
	}

	Main() throws IOException {
		Locale.setDefault(Locale.US);
		in = new BufferedReader(new FileReader("fourprimes.in"));
		out = new PrintWriter("fourprimes.out");
		solve();
		in.close();
		out.close();
	}

	String ns() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}

	int ni() throws IOException {
		return Integer.valueOf(ns());
	}

	double nd() throws IOException {
		return Double.valueOf(ns());
	}

	long nl() throws IOException {
		return Long.valueOf(ns());
	}

	void dbg(Object... objs) {
		if (!DEBUG) {
			return;
		}
		for (Object o : objs) {
			String printLine;
			if (o.getClass().isArray()) {
				printLine = arrayToString(o);
			} else {
				printLine = o.toString();
			}
			System.err.print(printLine + " ");
		}
		System.err.println();
	}

	String arrayToString(Object o) {
		if (o instanceof long[])
			return Arrays.toString((long[]) o);
		if (o instanceof int[])
			return Arrays.toString((int[]) o);
		if (o instanceof short[])
			return Arrays.toString((short[]) o);
		if (o instanceof char[])
			return Arrays.toString((char[]) o);
		if (o instanceof byte[])
			return Arrays.toString((byte[]) o);
		if (o instanceof double[])
			return Arrays.toString((double[]) o);
		if (o instanceof float[])
			return Arrays.toString((float[]) o);
		if (o instanceof boolean[])
			return Arrays.toString((boolean[]) o);
		if (o instanceof Object[])
			return Arrays.deepToString((Object[]) o);
		throw new IllegalStateException();
	}

	class Timer {

		long time;

		void start() {
			time = System.currentTimeMillis();
		}

		long time() {
			return System.currentTimeMillis() - time;
		}

		void print() {
			print("Time spent = ");
		}

		void print(String message) {
			dbg(message, time());
		}

	}

	public static void main(String[] args) throws IOException {
		new Main();

	}