UVA - 11137

 /*
       _________
      /         \
     /  _     _  \
    /   0     0   \
   |       ||     |
   |              | => HI
    \     -----   /
     \           /
      \_ _ _ _ _/
 */

#include<bits/stdc++.h>
using namespace std;
using lli = int64_t;
const int maxN = 10100;
int coins[] = {1,8,27,64,125,216,343,512,729,1000,1331,1728,2197,2744,3375,4096,4913,5832,6859,8000,9261};
lli grid[21][maxN];
lli solve(int idx,int n){
    if(idx == 21 or n == 0){
        return n == 0;
    }
    if(grid[idx][n] != -1){
        return grid[idx][n];
    }
    lli res = 0;
    for(int i = 0;i <= n; i++){
        if(n - (i * coins[idx]) >= 0){
            res += solve(idx + 1,n - (i * coins[idx]));
        }
    }
    return grid[idx][n] = res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    memset(grid,-1,sizeof(grid));
    while(cin >> n and EOF){
        cout << solve(0,n) << "\n";
    }
}