#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int INF = 1e9; const ll LINF = 1e18; template ostream& operator << (ostream& out,const pair& o){ out << "(" << o.first << "," << o.second << ")"; return out; } template ostream& operator << (ostream& out,const vector V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; } template ostream& operator << (ostream& out,const vector > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; } template ostream& operator << (ostream& out,const map mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; } /* 問題文============================================================ ================================================================= 解説============================================================= ================================================================ */ const ll MAX_PRIME = 500050; vector primes; vector is_prime(MAX_PRIME + 1,true); void init_primes(){ is_prime[0] = is_prime[1] = false; for(int i = 2; i <= MAX_PRIME;i++){ if(is_prime[i]){ primes.push_back(i); for(int j = i*2; j <= MAX_PRIME; j+=i) is_prime[j] = false; } } } int dp[4][MAX_PRIME]; int dp1[4][MAX_PRIME]; int dp2[4][MAX_PRIME]; ll solve(){ init_primes(); ll res = 0; ll N; cin >> N; dp[0][0] = 1; for(int i = 0; i < primes.size();i++){ if(N < primes[i]) continue; for(int j = 2; j >= 0;j--){ for(int k = 3*primes[i]; k >= 0;k--){ if(dp[j][k] == 0) continue; dp[j+1][k+primes[i]] += dp[j][k]; } } } for(int i = 0; i <= 3*N;i++){ if(is_prime[i]){ res += dp[3][i]; } } // ll Lim = upper_bound(primes.begin(),primes.end(),N) - primes.begin(); // dp1[0][0] = 1; // for(ll i = 0; i < Lim/2;i++){ // //if(N < primes[i]) continue; // for(int j = 2; j >= 0;j--){ // for(int k = 3*primes[i]; k >= 0;k--){ // if(dp1[j][k] == 0) continue; // dp1[j+1][k+primes[i]] += dp1[j][k]; // } // } // } // cout << "ok" << endl; // // dp2[0][0] = 1; // for(ll i = Lim/2; i < Lim;i++){ // for(int j = 2; j >= 0;j--){ // for(int k = 3*primes[i]; k >= 0;k--){ // if(dp2[j][k] == 0) continue; // dp2[j+1][k+primes[i]] += dp2[j][k]; // } // } // } // cout << "ok2" << endl; // for(ll k1 = 0; k1 <= 3*primes[Lim/2];k1++){ // for(ll k2 = 3*primes[Lim/2]; k2 <= 3*N;k2++){ // if(is_prime[k1+k2]){ // res += dp1[1][k1]*dp2[2][k2]; // res += dp1[2][k1]*dp2[1][k2]; // } // } // } // // for(int i = 0; i <= 3*N;i++){ // if(is_prime[i]){ // res += dp1[3][i]; // res += dp2[3][i]; // } // } // return res; } int main(void) { cin.tie(0); ios_base::sync_with_stdio(false); cout << solve() << endl; return 0; }