Ingenuous Cubrency UVA - 11137

/**
@author - Rumman BUET CSE'15
problem -  Ingenuous Cubrency UVA - 11137

*/
#include<bits/stdc++.h>
#define ll long long
#define fo freopen("out.txt","w",stdout)
#define fi freopen("in.txt","r",stdin)
#define DEBUG printf("hi\n");
#define DEBUG2 printf("bi\n");
#define pi acos(-1)
#define cube(a) a*a*a
//#define m 100000007
#define d 0.000000001

using namespace std ;

ll curr[100];
ll dp[25][2000000] ;


ll rec(ll i , ll n)
{
    if(n == 0)
    {
        return 1 ;
    }
    if(n < 0)
        return 0 ;
    if(i >= 21 && n > 0)
    {
        return 0 ;
    }

    if(dp[i][n]!=-1)
    {
        return dp[i][n] ;
    }

    return dp[i][n] = rec(i , n - curr[i]) + rec(i+1 , n) ;
}


int main()
{
    for(ll i = 1 ; i <= 21 ; i++)
    {
        curr[i-1] = cube(i)  ;
    }

    ll a ;
    memset(dp , -1 , sizeof(dp)) ;

    while(scanf("%lld",&a)!= EOF)
    {
        ll ans ;
        ans = rec(0 , a) ;
        printf("%lld\n" , ans) ;
    }

    return 0 ;
}