时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有 \(n\) 辆公交车，\(n\) 位司机和 \(n\) 位售票员，若要求每辆车配 1 位司机和 1 位售票员，则车辆、司机和售票员的搭配方案共有多少种？

【输入格式】

　　输入 \(n\)。

【输出格式】

　　输出方案数 \(mod\ 10^9+7\)。

【输入输出样例】

　Input

3

　Output

36

【数据限制】

　　对于100%的数据，满足：\(1 ≤ n ≤ 20\)。

【来源】

　　Mr.he