/*
#include <stdio.h>
int rec(int n)
{
if (n==1)
{
return 1;
}
return n + rec(n-1);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d",rec(n));
return 0;
}
*/
/*
#include <stdio.h>
int rec(int n)
{
if (n==1)
{
return 1;
}
return n*rec(n-1);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", rec(n));
return 0;
}
*/
/*
#include <stdio.h>
int memo[201]={};
int rec(int n)
{
if(memo[n]!=0)
{
return memo[n];
}
if (n==1||n==2)
{
return memo[n]=1;
}
return memo[n]=(rec(n-1)+rec(n-2))%10009;
}
int main ()
{
int n;
scanf("%d", &n);
printf("%d", rec(n));
return 0;
}
#include <stdio.h>
int memo[51][51]={0};
int rec(int r, int c)
{
if (memo[r][c]!=0)
{
return memo[r][c];
}
if (r==1||c==1)
{
return memo[r][c]=1;
}
else
{
return memo[r][c]=(rec((r-1),c)+rec(r, c-1))%100000000;
}
}
int main()
{
int r, c;
scanf("%d %d", &r, &c);
printf("%d", rec(r, c));
return 0;
}
*/
/*점화식 == 공식
f(n) 함수가 있을 때, f(1) 일때 성립하고, f(k) 그리고 f(k+1)
*sum
mysum(n) =>1부터 n까지의 합
=> 1+2+3+4+....+n
=> n + 1부터 n-1까지의 합
=> n + mysum(n-1)
*factorial
f(n) =>1부터 n까지의 곱
=>
*fibonacci
f(n) => 첫 번째 수와 두 번째 수는 모두 1이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다.
*/
/*
#include <stdio.h>
int memo[15][15]={};
int SuperSum(int k, int n)
{
if (memo[k][n]!=0)
{
return memo[k][n];
}
if (k==0)
{
return memo[k][n]=n;
}
if (n==1)
{
return memo[k][n]=1;
}
return memo[k][n]=SuperSum(k-1, n)+SuperSum(k, n-1);
}
int main()
{
int k, n;
while( scanf("%d %d", &k, &n) != EOF )
{
printf("%d\n", SuperSum(k, n));
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int arr[6], i, j, n;
for (i=1;i<=5;i++)
{
scanf("%d", &arr[i]);
}
for (i=1;i<5;i++)
{
for (j=1;j<=5-i;j++)
{
if (arr[j]>arr[j+1])
{
n=arr[j];
arr[j]=arr[j+1];
arr[j+1]=n;
}
}
}
for (i=1;i<=5;i++)
{
printf("%d ", arr[i]);
}
return 0;
}
#include <stdio.h>
int main()
{
int arr[6], i, j, n, k;
for (i=1;i<=5;i++)
{
scanf("%d", &arr[i]);
}
for (i=1;i<5;i++)
{
k=i;
for (j=i+1;j<=5;j++)
{
if (arr[j]<arr[k])
{
k=j;
}
}
n=arr[i];
arr[i]=arr[k];
arr[k]=n;
}
for (i=1;i<=5;i++)
{
printf("%d ", arr[i]);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int arr[6], n, k, i, j;
for (i=1;i<=5;i++)
{
scanf("%d", &arr[i]);
}
for (i=2;i<=5;i++)
{
k=arr[i];
for (j=i-1;arr[j]>=k && j>=1;j--)
{
arr[j+1]=arr[j];
}
arr[j+1]=k;
}
for (i=1;i<=5;i++)
{
printf("%d ", arr[i]);
}
return 0;
}
*/