#include <iostream>

using namespace std;
int n, st[100], y=0, p=0;
int bun(int k)
{
    int i;
    for(i=1;i<k;i++)
        if(st[i]==st[k])return 0;
    return(st[k]>st[k-1]+1 or st[k]<st[k-1]-1);
}
void afis()
{
    int i;
    if(y==0)
    {
        for(i=1;i<=n;i++)
            cout<<st[i]<<" ";
        y++;
    }
    p++;
}
void bkt()
{
    int k=1;
    while(k>0)
        if(st[k]<n)
    {
        st[k]++;
        if(bun(k))if(k==n)afis();
                    else k++;
    }
    else{
        st[k]=0;
        k--;
    }
}
int main()
{
    cin>>n;
    bkt();
    cout<<'\n'<<p;
    return 0;
}