#include <iostream>
#include <vector>

using namespace std;

typedef unsigned      Number;
typedef unsigned long Count;


constexpr Number   value   = 1024;
constexpr unsigned maxCoin = 512;

typedef vector<Count> Internal;
typedef vector<Internal> External;
External cache( maxCoin+1, Internal(value+1, 0) );

template<unsigned CFN>
Count cntFor(const Number n)
{
  if(cache[CFN][n])
    return cache[CFN][n];
  if(n<CFN)
    return cache[CFN][n] = cntFor<CFN/2>(n);
  return cache[CFN][n] = cntFor<CFN>(n-CFN) + cntFor<CFN/2>(n);
}

template<>
Count cntFor<1>(const Number n)
{
  return 1;
}

template<>
Count cntFor<2>(const Number n)
{
  if(n<=1)
    return 1;
  if(n<=2)
    return 2;
  return cntFor<2>(n-2) + cntFor<1>(n-1);
}

int main(void)
{
  const Number i = value;
  //for(Number i=1; i<=8; ++i)
    cout << i << " == " << cntFor<maxCoin>(i) << endl;
}