集合划分问题(1)

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

n个元素的集合{1,2,……, n }可以划分为若干个非空子集。例如,当n=4时,集合{1,2,3,4}可以划分为15个不同的非空子集如下:
 {{1},{2},{3},{4}},
 {{1,2},{3},{4}},
 {{1,3},{2},{4}},
 {{1,4},{2},{3}},
 {{2,3},{1},{4}},
 {{2,4},{1},{3}},
 {{3,4},{1},{2}},
 {{1,2},{3,4}},
 {{1,3},{2,4}},
 {{1,4},{2,3}},
 {{1,2,3},{4}},
 {{1,2,4},{3}},
 {{1,3,4},{2}},
 {{2,3,4},{1}},
 {{1,2,3,4}}
给定正整数n,计算出n个元素的集合{1,2,……, n }可以划分为多少个不同的非空子集。

Input

输入数据只有1行是元素个数n(n≤20)。

Output

输出一个整数,表示计算出的不同的非空子集数。

Sample Input

5

Sample Output

52

Hint

Source