#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;
}
}
ICAgI2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp2b2lkIGNhbWlub3MgKGludCxpbnQpOwppbnQgdGVzdCA9IDA7CiAKaW50IG1haW4oKXsKICAgIGludCBpPTAsbj0wOwogICAgY291dDw8Ikluc2VydGUgdGFtYcOxbyBkZSBsYSBSYXl1ZWxhOiAiOwogICAgY2luPj5uOwogICAgY2FtaW5vcyhpLG4pOwogICAgY291dCA8PCJDYW50aWRhZCBjYW1pbm9zOiIgPDwgdGVzdDsKICAgIApyZXR1cm4gMDsKfQp2b2lkIGNhbWlub3MgKGludCBpLGludCBuKXsKCQogICAgaWYoaTw9bil7CiAgICAgICAgY291dDw8aTsKICAgICAgICBjYW1pbm9zKGkrMSxuKTsKICAgICAgICBpZihpKzI8PW4pewogICAgICAgIAlpZiAoaSAhPSAwKXsKICAgICAgICAgICAgIGNvdXQ8PGk7CiAgICAgICAgCX0KICAgICAgICAgICAgIGNhbWlub3MoaSsyLG4pOwogICAgICAgICAgICB9CiAgICB9CiAgICBlbHNlewogICAgCXRlc3QrKzsKICAgICAgICBjb3V0PDxlbmRsOwogICAgICAgIGNvdXQ8PDA7CiAgICB9Cn0=