#include <iostream>
#include <map>

using namespace std;

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

int fibonacci(int i){
	//cout << "computing fibonacci(" << i << ")" << endl; 
	freq[i]++;
	if ((i==1)||(i==2)){
		memo[i] = 1;
		return 1;
	}

	int f_1, f_2;
	
	map<int,int>::iterator itr1 = memo.find(i-1);
	if (itr1!=memo.end())
		f_1 = itr1->second;
	else
		f_1 = fibonacci(i-1);	

	map<int,int>::iterator itr2 = memo.find(i-2);
	if (itr2!=memo.end())
                f_2 = itr2->second;
        else
                f_2 = fibonacci(i-2);
	
	memo[i]=f_1 + f_2;
	return f_1 + f_2;
}

int main(int argc, char** argv){
	if (argc!=2){
		cout << "parameters: n" << endl;
		return 1;
	}
	cout << fibonacci(atoi(argv[1])) << endl;
	for (map<int,int>::iterator itr=freq.begin(); itr!=freq.end(); itr++)
                cout  << itr->first << " :"  << itr->second << endl;
	
	return 0;
}