题目描述
嘉莹今天给她的亲友写了 n 封信，在写好之后她准备把 n 封信的信笺放入 n 个已经写好收件人信息的新风中。这时候她突然想玩一个游戏，她故意把信笺放错位置，她发现这个是一个有趣的数学问题。
经过钻研之后，她发现了这个问题的秘密，她能够快速的计算出 n 封信全部错误放入 n 个新风的方案总数。
现在，她拿着这个问题来考考你，你也也能快速算出来吗？

输入格式
一个整数 n ，表示有 n 封写好的信笺，也有 n 个写好收件人信息的信封。

数据范围
1 <= n <= 15
保证结果不超出 max long long

输出格式
一个整数，代表全部错放的方案总数。

样例

2

1

3

2

4

9

样例解释

1. 样例1：符合题目的方案有：1(2)-2(1) ,括号外的数字是代表信封，括号内的数字代表信笺。
2. 样例2：符合题目的方案有：1(2)-2(3)-3(1), 1(3)-2(1)-3(2) 。
3. 样例2：符合题目的方案有：
   • 1(2)-2(1)-3(4)-4(3)
   • 1(2)-2(3)-3(4)-4(1)
   • 1(2)-2(4)-3(1)-4(2)
   • 1(3)-2(1)-3(4)-4(2)
   • 1(3)-2(4)-3(1)-4(2)
   • 1(3)-2(4)-3(2)-4(1)
   • 1(4)-2(1)-3(2)-4(3)
   • 1(4)-2(3)-3(1)-4(2)
   • 1(4)-2(3)-3(2)-4(1)