看一下，包AC！

#include<iostream>
using namespace std;
int c[22]={0,0,1,2,9,44,265,1854,14833,133496,1334961};
int main(){
int t;
while(cin>>t){
cout<<c[t]<<endl;
}
}