题目描述

某人写了 $n$ 封信，在写好之后把 $n$ 封信的信笺放入 $n$ 个已经写好收件人信息的信封中。如果所有的信都装错了信封，共有多少种不同的情况？

输入格式

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

数据范围

$1 \le n \le 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)