/* 4345 */

 #include <iostream>

 #include <sstream>

 #include <string>

 #include <map>

 #include <queue>

 #include <set>

 #include <stack>

 #include <vector>

 #include <deque>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <ctime>

 #include <cstring>

 #include <climits>

 #include <cctype>

 #include <cassert>

 #include <functional>

 #include <iterator>

 #include <iomanip>

 using namespace std;

 //#pragma comment(linker,"/STACK:102400000,1024000")

 #define sti                set<int>

 #define stpii            set<pair<int, int> >

 #define mpii            map<int,int>

 #define vi                vector<int>

 #define pii                pair<int,int>

 #define vpii            vector<pair<int,int> >

 #define rep(i, a, n)     for (int i=a;i<n;++i)

 #define per(i, a, n)     for (int i=n-1;i>=a;--i)

 #define clr                clear

 #define pb                 push_back

 #define mp                 make_pair

 #define fir                first

 #define sec                second

 #define all(x)             (x).begin(),(x).end()

 #define SZ(x)             ((int)(x).size())

 #define lson            l, mid, rt<<1

 #define rson            mid+1, r, rt<<1|1

 const int maxn = ;

 bool isPrime[maxn];

 int P[maxn], pn = ;

 __int64 dp[maxn][];

 __int64 ans[maxn];

 void init() {

     memset(isPrime, true, sizeof(isPrime));

     rep(i, , maxn) {

         if (isPrime[i]) {

             P[pn++] = i;

             for (int j=i*i; j<maxn; j+=i)

                 isPrime[j] = false;

         }

     }

     #ifndef ONLINE_JUDGE

         printf("pn = %d\n", pn);

     #endif

     ans[] = ;

     rep(i, , ) {

         rep(j, , pn) {

             if (P[j] > i)

                 break;

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

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

             }

         }

         per(j, , )

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

         ans[i] = dp[i][] + ;

     }

     #ifndef ONLINE_JUDGE

         rep(i, , )

             printf("%d: %I64d\n", i, ans[i]);

     #endif

 }

 int main() {

     ios::sync_with_stdio(false);

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

         freopen("data.out", "w", stdout);

     #endif

     int n;

     init();

     while (scanf("%d", &n)!=EOF)

         printf("%I64d\n", ans[n]);

     #ifndef ONLINE_JUDGE

         printf("time = %d.\n", (int)clock());

     #endif

     return ;

 }