转眼毕业了，曾经朝夕相处的同学们不得不都各奔东西，大家都去了不同的城市开始新的生活。
在各自城市居住了一段时间后，他们都感到了一些厌倦，想去看看其他人的生活究竟如何，于是他们都选择到另一个同学所在城市去旅游，并且希望旅游的城市各不相同。
他们想知道有多少种不同的方案，可是数量实在太多了，他们无法计算出来，你能帮助他们吗。
一个正整数 n，表示人数。
一个数，表示有多少不同的方案。
3
2
样例说明：
假设原来各自居住的城市编号是：1，2，3。所有的排列有：
1 2 3 // 三个都选了自己的城市，不行 1 3 2 // 1选了自己的城市，不行 2 1 3 // 3选了自己的城市，不行 2 3 1 // 可以 3 1 2 // 可以 3 2 1 // 2选了自己的城市，不行
所以，每个人都旅行到不同城市的方案有：2、3、1 和 3、1、2两种。
70% 数据：2 ≤ n ≤ 10
100% 数据：2 ≤ n ≤ 20