#include <iostream>
#include <map>
#include <unordered_map>

using namespace std;

map<pair<int,int>,int> freq;
map<pair<int,int>,int> memo;

int choose(int n, int k){
	//cout << "computing choose(" << n << "," << k << ")" << endl;
	freq[make_pair(n,k)]++;
	if (k==n){
		memo[make_pair(n,k)]=1;
		return 1;
	}
	if (k==1){
		memo[make_pair(n,k)]=1;
		return n;
	}
	
	int c_1, c_2;

        map<pair<int,int>,int>::iterator itr1 = memo.find(make_pair(n-1,k));
        if (itr1!=memo.end())
                c_1 = itr1->second;
        else
                c_1 = choose(n-1,k);

        map<pair<int,int>,int>::iterator itr2 = memo.find(make_pair(n-1,k-1));
        if (itr2!=memo.end())
                c_2 = itr2->second;
        else
                c_2 = choose(n-1,k-1);

	memo[make_pair(n,k)] = c_1 + c_2;
	return c_1 + c_2;
}


int main(int argc, char** argv){
	if (argc!=3){
		cout << "parameters: n and k" << endl;
		return 1;
	}

	cout <<"result:" << choose(atoi(argv[1]), atoi(argv[2])) << endl;

	cout << "counts: " << endl;
	for (map<pair<int,int>,int>::iterator itr=freq.begin(); itr!=freq.end(); itr++){
		pair<int,int> key = itr->first;
		int value = itr->second;
		cout << "(" << key.first << "," << key.second << "): " << value << endl;
	}
	return 0;
}