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

---

【题目描述】

　　联合国大会在举行，\(n\) 个国家的元首参加，他们围坐在一个大圆桌上，但是其中美俄罗两国不愿批次挨着坐，试问有多少种循环座位排放法？

【输入格式】

　　一个正整数 \(n\)。

【输出格式】

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

【输入输出样例】

　Input

5

　Output

12

【数据限制】

　　对于 \(100\%\) 的数据，\(n≤100\)

【来源】

　　Mr.he**