/*#include <stdio.h>
long long int n;
int sqrt(long long int n)
{
int i,k=0;
for(i=0;i<=n;i++)
{
if((long long int)i*i>n)
{
k=i-1;
break;
}
else if((long long int)i*i==n)
{
k=i;
break;
}
}주위의 이웃이 y 미만이거나 z 이상이면 죽고, y 이상 z 미만이면 산다
return k;
}
int main()
{
scanf("%lld", &n);
printf("%d\n", sqrt(n));
return 0;
}*//*
#include<stdio.h>
int main()
{
int h,q,w,a,b,x,y,z,arr1[180][180]={},arr2[180][180]={},k,i,j,c=0;
scanf("%d %d",&a,&b);
scanf("%d %d %d",&x,&y,&z);
for(i=1;i<=a;i++)
{
for(j=1;j<=b;j++)
{
scanf("%d ",&arr1[i][j]);
}
}
scanf("%d",&k);
for(h=1;h<=k;h++)
{
if(h%2!=0)
{
for(i=1;i<=a;i++)
{
for(j=1;j<=b;j++)
{
c=0;
for(q=-1;q<=1;q++)
{
for(w=-1;w<=1;w++)
{
c+=arr1[i+q][j+w];
}
}
c-=arr1[i][j];
if(arr1[i][j]==1)
{
if(c<y || c>=z)
{
arr2[i][j]=0;
}
else if(c>=y && c<z)
{
arr2[i][j]=1;
}
else
{
arr2[i][j]=1;
}
}
else
{
if(c==x)
{
arr2[i][j]=1;
}
else
{
arr2[i][j]=0;
}
}
}
}
}
else
{
for(i=1;i<=a;i++)
{
for(j=1;j<=b;j++)
{
c=0;
for(q=-1;q<=1;q++)
{
for(w=-1;w<=1;w++)
{
c+=arr2[i+q][j+w];
}
}
c-=arr2[i][j];
if(arr2[i][j]==1)
{
if(c<y || c>=z)
{
arr1[i][j]=0;
}
else if(c>=y && c<z)
{
arr1[i][j]=1;
}
else
{
arr1[i][j]=1;
}
}
else
{
if(c==x)
{
arr1[i][j]=1;
}
else
{
arr1[i][j]=0;
}
}
}
}
}
}
if(k%2!=0)
{
for(i=1;i<=a;i++)
{
for(j=1;j<=b;j++)
{
printf("%d ",arr2[i][j]);
}
printf("\n");
}
}
else
{
for(i=1;i<=a;i++)
{
for(j=1;j<=b;j++)
{
printf("%d ",arr1[i][j]);
}
printf("\n");
}
}
return 0;
}1565 1602*/
/*#include <stdio.h>
int gcd(int p, int q)
{
if(p==0)
return q;
return gcd(q%p, p);
}
long long int lcm(int a, int b)
{
long long int k,q,w;
k=gcd(a, b);
q=a/k;
w=b/k;
return k*q*w;
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
printf("%lld\n", lcm(a, b));
}*/
/*
#include<stdio.h>
double f(double k)
{
if(k<0)
{
return -k;
}
else
{
return k;
}
}
int main()
{
double a;
scanf("%lf",&a);
printf("%.10g",f(a));
}*/
//재귀함수 recursive function 순환함수
//함수 안에서 자기 자신을 다시 호출하는함수
/*
#include <stdio.h>
void rec(int n)
{
if(n==0) return ;//종료조건
rec(n-1);
printf("%d ",n);
}
int main()
{
rec(4);
return 0;
}
*//*
#include<stdio.h>
int n;
void rec(int k)
{
if(k==n+1)
{
return;
}
printf("%d\n",k);
rec(k+1);
}
int main()
{
scanf("%d",&n);
rec(1);
return 0;
}*//*
#include<stdio.h>
void rec(int k)
{
if(k==0)
{
return;
}
printf("%d\n",k);
rec(k-1);
}
int main()
{
int n;
scanf("%d",&n);
rec(n);
return 0;
}*//*
#include<stdio.h>
int a,b;
void rec(int k)
{
if(k==b+1)
{
return ;
}
if(k%2!=0)
{
printf("%d ",k);
rec(k+1);
}
else
{
rec(k+1);
}
}
int main()
{
scanf("%d %d",&a,&b);
rec(a);
return 0;
}*//*
#include<stdio.h>
int n;
int rec(int k)
{
if(k==1) return 1;
return rec(k-1)+k;
}
int main()
{
scanf("%d",&n);
printf("%d",rec(n));
return 0;
}*//*
#include<stdio.h>
int rec(int k)
{
if(k==1) return 1;
return rec(k-1)*k;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",rec(n));
}*//*
#include<stdio.h>
int N;
int rec(int k)
{
if(k==1 || k==2) return 1;
return rec(k-1)+rec(k-2);
}
int main()
{
scanf("%d",&N);
printf("%d",rec(N));
}
1928 1920
*/