#include <iostream>
using namespace std;
void caminos (int,int);
int test = 0;
 
int main(){
    int i=0,n=0;
    cout<<"Inserte tamaño de la Rayuela: ";
    cin>>n;
    caminos(i,n);
    cout <<"Cantidad caminos:" << test;
    
return 0;
}
void caminos (int i,int n){
	
    if(i<=n){
        cout<<i;
        caminos(i+1,n);
        if(i+2<=n){
        	if (i != 0){
             cout<<i;
        	}
             caminos(i+2,n);
            }
    }
    else{
    	test++;
        cout<<endl;
        cout<<0;
    }
}