#include <stdio.h>char b[1000][1000];int main(){ int i,j,ttt; for(i=0;i<1000;i++) for(j=0;j<1000;j++) b[i][j]='#'; int u=0,t=1,s=0,tt,mt,bt,nn; char ct; b[0][0]='1'; for(i=1;i<1000;i++) { u=0; mt=t; for(j=0;j<mt;j++) { if(b[i-1][j]=='#') bt=0; else bt=b[i-1][j]-'0'; tt=bt; s=tt*2+u; if(j==(t-1)&&s>=10){t++;b[i][j+1]='1';} u=s/10; s=s%10; ct='0'+s; b[i][j]=ct; } u=0; if(i%2!=0) { if(b[i][0]=='0') { b[i][0]='9'; b[i][1]=b[i][1]-1; } else { s=b[i][0]-'0'; s=s-1; ct=s+'0'; b[i][0]=ct; } } else { s=b[i][0]-'0'; s=s+1; ct=s+'0'; b[i][0]=ct; } } while(scanf("%d",&nn)!=-1) { if(nn==1||nn==0)printf("0n"); else if(nn==3||nn==2)printf("1n"); else { int count=0; for(ttt=0;ttt<1000;ttt++) if(b[nn-2][ttt]!='#') count=ttt; for(i=count;i>=0;i--) printf("%c",b[nn-2][i]); printf("n"); } }}
