/*
#include<stdio.h>
int n,ar[100][100]={},count=0,check[14]={};
int cross(int k,int l)
{
int i,temp=0;
for(i=1;;i++)
{
if((k+i>n||l+i>n)&&(k-i<1||l-i<1)) break;
if(ar[k+i][l+i]==1||ar[k-i][l+i]==1||ar[k+i][l-i]==1||ar[k-i][l-i]==1){
temp++;
}
}
printf(" %d %d %d\n",k,l,temp);
if(temp==0) return 0;
else return 1;
}
void find(int k,int l)
{
int i;
ar[k][l]=1;
if(check[k]==1||cross(k,l)==1) return;
check[k]=1;
if(l==6){
count++;
if(count>=1&&count<=3){
view();
}
pop();
}
else{
for(i=1;i<=n;i++)
{
if(i==k) continue;
find(i,l+1);
}
}
}
void view()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(ar[i][j]==1){
printf("%d ",j);
}
}
}
}
void pop()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
ar[i][j]=0;
check[i]=0;
}
}
}
int main()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
find(i,1);
}
printf("%d",count);
return 0;
}
*/
/*
#include<stdio.h>
int n,arr[15]={},count=0;
int is_okay(int k, int l)
{
int i;
for(i=1;i<k;i++){
if(arr[i]==l) return 0;
if(arr[i]-i==l-k) return 0;
if(arr[i]-l==k-i) return 0;
}
return 1;
}
void find(int k)
{
int i;
if(k==n+1){
count++;
if(count<=3){
for(i=1;i<=n;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
}
for(i=1;i<=n;i++)
{
if(is_okay(k,i)==1){
arr[k]=i;
find(k+1);
}
}
}
int main()
{
scanf("%d",&n);
find(1);
printf("%d",count);
}
*/
/*
#include<stdio.h>
long long int memo[100001]={};
int main()
{
long long int n,i,sum=0;
scanf("%lld",&n);
for(i=1;i<=n;i++)
{
memo[i]+=i+memo[i-1];
sum+=(memo[i])%100000007;
}
printf("%lld",sum%100000007);
return 0;
}
*/
/*
#include<stdio.h>
int stack[32]={};
int top=-1;
void push(int n)
{
top++;
stack[top]=n;
}
void pop()
{
if(top==-1) return;
top--;
}
int main()
{
int i,count1=0,count2=0,top1=-1,temp=1,okay=1,sum=0;
char a[32]={};
scanf("%s",a);
for(i=0;i<strlen(a);i++)
{
if(a[i]=='('){
count1++;
top1++;
temp*=2;
}
if(a[i]=='['){
count2++;
top1++;
temp*=3;
}
if(a[i]==')'){
if(count1<=0){
okay=0;
}
if(a[i-1]=='('){
push(temp);
}
count1--;
top1--;
temp/=2;
}
if(a[i]==']'){
if(count2<=0){
okay=0;
}
if(a[i-1]=='['){
push(temp);
}
count2--;
top1--;
temp/=3;
}
if(top<-1){
okay=0;
}
}
if(okay==0||top1!=-1){
printf("0");
return 0;
}
for(;;)
{
sum+=stack[top];
pop();
if(top==-1) break;
}
printf("%d",sum);
return 0;
}
*/