/*
#include <stdio.h>
double f(long long int n){
double a=0,b=100000000*n,c=-1;
double k=0.000001;
while(b-a>k){
c=(a+b)/2;
if(c*c>100000000*n) b=c;
else a=c;
//printf("%.15g %.15g %.15g %lld\n",a,b,c,n);
//printf("%.10lf %.10lf %.10lf %lld\n",a,b,c,n);
}
return c;
}
int main()
{
int t,i;
long long int n;
scanf("%d",&t);
for(i=0;i<t;i++){
scanf("%lld",&n);
printf("%.8lf\n",f(n)/10000);
}
return 0;
}
//1234567.12345678902
//1234567.12345678901
*/
/*
#include <stdio.h>
int arr[10000001]={};
int main(){
int max=0,q=0;
int a,b,p;
long long int n;
scanf("%d %d",&a,&b);
for(int i=a;i<=b;i++){
n=i;
if(arr[n]!=0) p=arr[n];
else{
p=1;
while(n!=1){
if(n<=10000000&&arr[n]!=0){
p+=arr[n]-1;
break;
}
if(n%2==0) n/=2;
else n=3*n+1;
p++;
}
}
arr[i]=p;
if(p>q){
q=p;
max=i;
}
}
printf("%d %d",max,q);
return 0;
}*/
/*
#include <stdio.h>
int main()
{
int n,i,j,k,a,b,t,s;
int arr[100001]={};
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&arr[i]);
}
k=arr[0]+arr[1];
if(k<0) k*=-1;
a=arr[0];
b=arr[1];
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(k==0) break;
s=arr[i]+arr[j];
if(s==0){
k=0;
a=arr[i];
b=arr[j];
break;
}
else if(k==s||k==-1*s) continue;
else if(s>0){
if(s<k){
k=s;
a=arr[i];
b=arr[j];
}
else continue;
}
else if(s<0){
if(-1*s<k){
k=-1*s;
a=arr[i];
b=arr[j];
}
else continue;
}
}
}
if(a>b){
t=a;
a=b;
b=t;
}
printf("%d %d",a,b);
return 0;
}
*/
//https://codeup.kr/classop.php?class_id=11386
/*
#include <stdio.h>
int main()
{
int i,j,n,r,t,ma,mi;
long long int k=1;
int a[10001]={},b[10001]={};
scanf("%d %d",&n,&r);
t=n-r;
if(t>r){
ma=t;
mi=r;
}
else{
ma=r;
mi=t;
}
for(i=ma+1;i<=n;i++) a[i]=i;
for(j=1;j<=mi;j++) b[j]=j;
for(i=ma+1;i<=n;i++){
for(j=2;j<=mi;j++){
for(int z=2;z*z<=b[j];z++){
if(a[j]<z) break;
if(a[j]%z==0&&b[j]%z==0){
a[j]/=z;
b[j]/=z;
}
}
}
}
for(i=ma+1;i<=n;i++){
if(a[i]==1) continue;
else k*=a[i];
}
for(j=2;j<=mi;j++){
if(b[j]==1) continue;
k/=b[j];
}
k%=100000007;
printf("%lld",k);
}
*/
//f(n,r) : nCr값 리턴
// : f(n-1,r)+f(n-1,r-1);
/*
#include <stdio.h>
int f(int n,int r){
if(r==1) return n;
if(n==r) return 1;
return f(n-1,r)+f(n-1,r-1);
}
int main()
{
int n,r,k;
scanf("%d %d",&n,&r);
k=f(n,r);
printf("%d",k);
return 0;
}
*/
/*
#include <stdio.h>
int arr[10001][10001]={};
int f(int n,int r){
if(r==1){
arr[n][r]=n;
return n;
}
if(n==r){
arr[n][r]=1;
return 1;
}
if(arr[n][r]!=0) return arr[n][r];
return f(n-1,r)%100000007+f(n-1,r-1)%100000007;
}
int main()
{
int n,r,t,k;
scanf("%d %d",&n,&r);
t=n-r;
if(t<r) r=t;
k=f(n,r)%100000007;
printf("%d",k);
return 0;
}
*/