#include <bits/stdc++.h>
using namespace std;
int aa[30], bb[30], cc[30], ans, n;
void dfs(int a, int b, int c)
{
    if(c == n)
    {
        ans++;
        for(int i = 1; i <= n; i++) printf("%d ", cc[i]);
        printf("\n"); 
    }
    else
    {
        if(a > 0)
        {
            bb[b + 1] = aa[a];
            aa[a] = 0;
             
            dfs(a - 1, b + 1, c);
             
            aa[a] = bb[b + 1];
            bb[b + 1] = 0;
        }
        if(b > 0)
        {
            cc[c + 1] = bb[b];
            bb[b] = 0;
             
            dfs(a, b - 1, c + 1);
             
            bb[b] = cc[c + 1];
            cc[c + 1] = 0;
        }
    }
}
int main()
{
    scanf("%d", &n);
    for(int i = n; i >= 1; i--) aa[i] = n - i + 1;
    ans = 0; dfs(n, 0, 0);
    printf("%d\n", ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int aa[30],bb[30],cc[30],ans,n;
void dfs(int a,int b,int c)
{
    if(c==n)
    {
        ans++;
        for(int i=1;i<=n;i++) printf("%d ",cc[i]);
        printf("\n"); 
    }
    else
    {
        if(a>0)
        {
            bb[ b+1 ]=aa[a];
            aa[a]=0;
             
            dfs(a-1,b+1,c);
             
            aa[a]=bb[ b+1 ];
            bb[ b+1 ]=0;
        }
        if(b>0)
        {
            cc[c+1]=bb[ b ];
            bb[ b ]=0;
             
            dfs(a,b-1,c+1);
             
            bb[ b ]=cc[c+1];
            cc[c+1]=0;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=n;i>=1;i--)aa[i]=n-i+1;
    ans=0;dfs(n,0,0);
    printf("%d\n",ans);
    return 0;
}