/*#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}*/
/*#include<stdio.h>
int sum=0;
int self(int n)
{
sum=n;
if(n>=1000)
{
sum+=n/1000;
n%=1000;
}
if(n>=100)
{
sum+=n/100;
n%=100;
}
if(n>=10)
{
sum+=n/10;
n%=10;
}
return sum=sum+n;
}
int main()
{
int a,b,arr[5001]={};
scanf("%d %d",&a,&b);
for(int i=a; i<=b; i++)
{
arr[self(i)]=1;
if(!arr[i])
sum=sum+i;
}
printf("%d",sum);
return 0;
}
*/
/*#include<stdio.h>
#include<string.h>
int main()
{
char n[101];
int z,k=0;
scanf("%s",n);
k=strlen(n);
for(z=0; z<k; z++)
{
if(n[z+1]=='d')
{
if(n[z+2]=='o'&&n[z+3]=='c')
{
if(n[z+4]=='x')
{
printf("Word.Document.12");
break;
}
printf("Word.Document.8");
}
if(n[z+2]=='i'&&n[z+3]=='b')
{
printf("Paint.Picture");
}
}
if(n[z+1]=='h')
{
if(n[z+2]=='t'&&n[z+3]=='m')
{
if(n[z+4]=='l')
{
printf("htmlfile");
break;
}
printf("htmfile");
}
if(n[z+2]=='w')
{
if(n[z+3]=='p')
{
if(n[z+4]=='x')
{
printf("Hwp.Document.hwpx.96");
break;
}
printf("Hwp.Document.96");
}
if(n[z+3]=='t')
{
printf("Hwp.Document.hwt.96");
}
}
}
if(n[z+1]=='j'&&n[z+2]=='p')
{
if(n[z+3]=='e')
{
if(n[z+4]=='g')
{
printf("jpegfile");
break;
}
printf("jpegfile");
}
if(n[z+3]=='g')
{
printf("jpegfile");
}
}
if(n[z+1]=='p'&&n[z+2]=='p'&&n[z+3]=='t')
{
if(n[z+4]=='x')
{
if(n[z+5]=='m'&&n[z+6]=='l')
{
printf("powerpointxmlfile");
break;
}
printf("PowerPoint.Show.12");
break;
}
printf("PowerPoint.Show.8");
}
}
return 0;
}
*/
/*#include<stdio.h>
int main()
{
int tmp = 0, count, num,i,j;
scanf("%d %d", &count, &num);
int c = count;
long long int arr[num];
for(i= 0; i<c; i++)
{
scanf("%lld", &arr[i]);
}
for(i=c;i<num;i++)
{
arr[i]=0;
}
for(i=c; i<num;i++)
{
for(j=tmp;j<tmp+c;j++)
{
arr[i]+=arr[j]%100007;
}
tmp++;
}
printf("%lld", arr[num-1]%100007);
return 0;
}
*/
/*#include<stdio.h>
int memo[100001]= {};
long long int d[100001]= {};
int fibo(int k,int n)
{
int m=0;
for(int i=k; i<n; i++)
{
d[i]=0;
}
for(int i=0; i<n; i++)
{
for(int j=m; i<m+k; j++)
{
d[i]+=d[j];
}
m++;
}
return memo[n]=d[n-1]%100007;
}
int main()
{
int k,n;
scanf("%d %d",&k,&n);
for(int i=0; i<k; i++)
{
scanf("%lld",&d[i]);
}
printf("%d",fibo(k,n));
return 0;
}*/