/*#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*#include<stdio.h>
int memo[10001] = {0,0,0,2};
int block(int k)
{
if(memo[k]!= 0)
{
return memo[k];
}
return memo[k] = (block(k - 3) * 2) % 100000007;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",block(n));
return 0;
}*/
/*#include<stdio.h>
int memo[21]={1,2};
int stairs(int k)
{
if(k==1)
{
return memo[k]=1;
}
if(k==2)
{
return memo[k]=2;
}
return stairs(k-2)+stairs(k-1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",stairs(n));
}*/
/*#include<stdio.h>
int battery(int a,int b)
{
}
int main()
{
int n,i,j,arr[5001][11],sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<6;j++)
{
scanf("%d",&arr[i][j]);
}
}
sum=sum+battery(n,arr[i][j]);
printf("%d",sum);
}*/
/*#include<stdio.h>
int main()
{
int n,sum=0,max=0;
int arr[5001][11]= {};
scanf("%d",&n);
for(int i=0; i<n; i++)
{
for(int j=0; j<6; j++)
{
scanf("%d",&arr[i][j]);
}
}
for(int j=0; j<6; j++)
{
max = 0;
for(int i=0; i<n; i++)
{
if(arr[i][j]>max)
{
max=arr[i][j];
}
}
sum=sum+max;
}
printf("%d",sum);
}*/
/*#include<stdio.h>
int memo[101]={};
int points(int k)
{
if(k==1)
{
return 5;
}
return memo[k]=points(k-1)+(k*3+1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",points(n));
}
*/
/*#include<stdio.h>
int memo[10000001]= {0, 5, 12, 22, };
int f(int k)
{
if(k==1)
{
return 5;
}
if()
{
}
return memo[k]=(f(k-1)+(k*3+1))%1000000004;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}*/