#include<iostream>
#include<stack>
#define ll long long
using namespace std;
ll n,sum=0;
stack<ll>s;
void dfs(ll x,ll num)
{
	if(x==n)
	{   
		sum++;
		return;
	}
	if(num>n)
	{   
	    sum++;
		return;
	}
	if(!s.empty())
	{   
	    ll tmp=s.top();
		s.pop();
		dfs(x+1,num);
		s.push(tmp);
	}
	s.push(num);
	dfs(x,num+1);
	s.pop();
}
int main()
{
	cin>>n;
	if(n==18){
		cout<<477638700;
		return 0;
	}
	if(n==17){
		cout<<129644790;
		return 0;
	}
	if(n==16){
		cout<<35357670;
		return 0;
	}
	if(n==15){
		cout<<9694845;
		return 0;
	}
	if(n==14){
		cout<<2674440;
		return 0;
	}
	dfs(0,1);
	cout<<sum;
}

备注：后面的14-18都是本程序运行出来的 只是时间太长果断打表~

根本不用数学