程序代码：

#include <iostream>
using namespace std;

typedef long long INT64;

INT64 _dp[30][30];

struct {
    INT64* operator [] (int i){
        return _dp[i];
    }    
}dp;

INT64 arr[30];

int main()
{
    arr[1]=arr[0]=dp[0][0]=1;
    for(int i=1;i<30;i++){
        dp[i][0]=dp[i-1][i-1];
        for(int j=1;j<=i;j++){
            dp[i][j]=dp[i-1][j-1]+dp[i][j-1];
        }  
        arr[i+1]=dp[i][i];  
    }
    int n;
    while(cin>>n){
        cout<<arr[n]<<endl;
    }    
}