#include<stdio.h>
int n;
int a[1000];
int check(int v,int k){
if(a[k-1]+v<=1) return 1;
else return 0;
}
void print(int k){
for(int i=0;i<=k;i++){
}
}
void Try(int k){
for(int i=0;i<=1;i++){
if(check(i,k)){
a[k]=i;
if(k==n-1) print(k);
else Try(k+1);
}
}
}
int main(){
Try(0);
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KaW50IG47CmludCBhWzEwMDBdOwppbnQgY2hlY2soaW50IHYsaW50IGspewogICAgaWYoYVtrLTFdK3Y8PTEpIHJldHVybiAxOwogICAgZWxzZSByZXR1cm4gMDsKfQp2b2lkIHByaW50KGludCBrKXsKICAgIGZvcihpbnQgaT0wO2k8PWs7aSsrKXsKICAgICAgICBwcmludGYoIiVkIixhW2ldKTsKICAgIH0KICAgIHByaW50ZigiXG4iKTsKfQp2b2lkIFRyeShpbnQgayl7CiAgICBmb3IoaW50IGk9MDtpPD0xO2krKyl7CiAgICAgICAgaWYoY2hlY2soaSxrKSl7CiAgICAgICAgYVtrXT1pOwogICAgICAgIGlmKGs9PW4tMSkgcHJpbnQoayk7CiAgICAgICAgZWxzZSBUcnkoaysxKTsKICAgICAgICB9CiAgICB9Cn0KaW50IG1haW4oKXsKICAgIHNjYW5mKCIlZCIsJm4pOwogICAgVHJ5KDApOwogICAgcmV0dXJuIDA7Cn0=