/*
#include <stdio.h>
int memo[51][51]={};
int f(int r, int c)
{
if(memo[r][c]!=0) return memo[r][c];
if(r==1||c==1) memo[r][c]=1;
else memo[r][c]=(f(r-1,c)+f(r,c-1))%100000000;
return memo[r][c];
}
int main()
{
int r,c;
scanf("%d %d",&r,&c);
printf("%d",f(r,c));
return 0;
}
*/
/*
#include <stdio.h>
int memo[201]={};
int f(int n)
{
if(memo[n]!=0) return memo[n];
if(n<=2) memo[n]=1;
else memo[n]=(f(n-1)+f(n-2))%10009;
return memo[n];
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
*/
/*
#include <stdio.h>
int memo[100001]={};
int f(int n)
{
if(memo[n]!=0) return memo[n];
if(n==1) memo[n]=1;
else if(n==2) memo[n]=2;
else if(n==3) memo[n]=4;
else memo[n]=(f(n-3)+f(n-2)+f(n-1))%1000;
return memo[n];
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
*/
/*
#include <stdio.h>
int stack[100];
int top=-1; //마지막으로 데이터가 들어온 곳의 위치
void push(int data)
{
stack[++top]=data;
}
int pop()
{
return stack[top--];
}
int main()
{
push(1);
push(4);
push(2);
printf("%d",pop());
}
*/
/*
#include <stdio.h>
char stack[201];
int top=-1;
void push(char data)
{
stack[++top]=data;
}
char pop()
{
return stack[top--];
}
int main()
{
char str[201];
int n,i;
scanf("%d",&n);
scanf("%s",str
);
for(i=n-1; i>=0; i--)
{
push(str[i]);
}
for(i=0; i<n; i++)
{
if(top%3==2&&i!=0) printf(",");
printf("%c",pop());
}
return 0;
}
*/
/*
#include <stdio.h>
int stack[100001];
int top=-1; //top : 마지막으로 입력된 데이터의 위치
void push(int data)
{
stack[++top]=data;
}
int pop()
{
return stack[top--];
}
void view()
{
printf("stack : ");
for(int i=0;i<=top;i++)
{
printf("%d ",stack[i]);
}
printf("\n");
}
int main()
{
int k,i,a,sum=0;
scanf("%d",&k);
for(i=k;i>=1;i--)
{
scanf("%d",&a);
if(a!=0)
{
push(a);
}
else
{
pop();
}
view();
}
while(top!=-1)
{
sum+=pop();
}
printf("%d",sum);
return 0;
}
*/
/*
#include <stdio.h>
int top=0;
int main()
{
int i;
char str[50001];
scanf("%s",str);
for(i=0;str[i]!=NULL;i++)
{
if(str[i]=='(') top++;
else
{
top--;
if(top<0)
{
printf("bad");
return 0;
}
}
}
if(top!=0)
{
printf("bad");
}
else
{
printf("good");
}
return 0;
}
*/
/*
#include <stdio.h>
int top=0;
int main()
{
char str[100001];
int i,sum=0;
scanf("%s",str);
for(i=0;str[i]!=NULL;i++)
{
if(str[i]=='('&&str[i+1]==')') sum+=top;
else if(str[i]=='(') top++;
else if(str[i]==')'&&str[i-1]!='(')
{
top--;
sum++;
}
}
printf("%d",sum);
return 0;
}
*/
/*
#include <stdio.h>
char stack1[101],stack2[101];
int top1=-1,top2=-1;
void push(char data)
{
}
char pop()
{
return stack[top1--];
}
char pop1()
{
return stack[top2--];
}
int main()
{
char str1[101],str2[101];
int i,num,c=0;
scanf("%s %s",str1,str2);
for(i=strlen(str1)-1; i>0; i--)
{
stack1[++top1]=str1[i];
}
for(i=strlen(str2)-1; i>0; i--)
{
stack2[++top2]=str2[i];
}
while(top1!=-1||top2!=-1)
{
num=c+pop()+pop1()-96;
push(num%10);
c=num/10;
}
}*/