题目：

集合A(1≤∣A∣≤100)上不同的等价关系一共多少个？

输入格式:

一行，一个整数n（1≤n≤100），表示集合A的元素个数。

输出格式:

集合A上不同等价关系的个数模109+7，即输出其个数模1000000007。（因为当∣A∣比较大时，A上的等价关系数是个巨大的数字，比如∣A∣=100时，其上等价关系的个数是个116位的数字。）

输入样例1:

4

输出样例1:

15

输入样例2:

30

输出样例2:

272358185

题解： 首先说说什么是等价关系。如果关系R是集合A上的关系，并且关系R满足自反，对称，传递。那么关系R就是A上的等价关系。 然后再说说什么是等价类。如果[x]R={y|y∈A ∧ \wedge ∧∈R}，则[x]R就是集合A上的等价类。

那么这个等价类和等价关系有什么关系呢，听着有点拗口嗷。 举个例子：设A={0，1，2，3，4，5，8，9}，R是A上以4为模的同余关系，求R所有等价类。 这是课本上的一个例题，答案是[0] = [4] = [8] = {0,4,8}，[1] = [5] = [9] = {1,5,9}，[2] = {2}。也就是有3个等价关系。

举的例子可能不够好，我是想说明，有的[x]可能是相等的集合，也就是说等价关系的个数就小于等于集合元素的个数。多个等价类是一个集合能想到什么呢？像是编号的小球放在不编号的盒子里并且盒子不空呢。这样一说是不是有那么一点点模糊的思路啦。

那么我们来想一下，都有哪几种可能性呢。 比如集合有4个元素，他的等价关系有多少种呢。可以想一下，假设所有的元素都属于一个等价类，那就只有一种。假设所有元素属于两个等价类，就会有6种。假设所有元素属于三个等价类，有7种，属于4个等价类的话，就只有1种。把所有可能加起来就是1 + 6 + 7 + 1 = 15种。求到答案了。

那么分析一下小球放在盒子里有什么规律吧，如果只有一个盒子的话，只可能有一种放法；如果盒子和小球的个数相等，那也是只有一种放法；如果小球数量比盒子还少呢，那就没有意义了对吧。 如果是三个小球放在两个盒子里呢，那必然有一个盒子是有两个球的，这个两个球的盒子可能是{1，2}，{2，3}，{1，3}三种可能。如果是4个小球放在2个盒子里呢，可能是两个两个一类{1，2}，{1，3}，{1，4}，也有可能事三个一个一类，{1，2，3}，{1，2，4}，{1，3，4}，{2，3，4}也就是一共七种。 如果多打一点表的话就会是这样（行号表示盒子数，列号表示球数，比如**[2][3]**表示3个球放在两个盒子里）： 假设小球有n个，盒子有r个，（n，r） =（n - 1, r - 1) + (n, r - 1) * r 这样就推出这个递推公式了，分析一下，每个（n,r）都是 (n - 1, r - 1)的基础上加上多一个小球一个盒子之后多出来的可能性。而这个可能性也就是不加球只加一个盒子的情况乘以盒子的数量。有了这个递推公式，程序就很好写了。

C++版：