#include<iostream>

 using namespace std;

 int n;

 const int maxn=;

 bool note[maxn+];

 long long  p[maxn];

 long long  dp[maxn][maxn];

 long long  tot;

 int pre()

 {

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

     {

         if(!note[i])

         {

             p[++tot]=i;

         }

         for(int j=;j<=tot&&i*p[j]<=n;j++)

         {

             note[i*p[j]]=;

             if(i%p[j]==)

             {

                 break;

             }

         }

     }

 }

 int main()

 {

     cin>>n;

     pre();

     for(int i=;i<=tot;i++)

     {

         dp[i][]=;

     }

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

     {

         dp[][i]=;

     }

     for(int i=;i<=tot;i++)

     {

         for(int j=;j<=n;j++)

         {

             dp[i][j]=dp[i-][j];

             for(int k=p[i];k<=j;k*=p[i])

             {

                 dp[i][j]+=dp[i-][j-k];

             }

         }

     }

     cout<<dp[tot][n]<<endl;

     return ;

 }