#4714. 旋转排列

题目描述


输入格式

输入仅有一行，包含一个整数n,1≤n≤500000

输出格式

输出一行，包含一个整数，代表答案。

样例

样例输入

4

样例输出

9  

【样例解释】  

k=2时的方案数为3，k=4时的方案数为6，k=1和k=3时的答案为0。  

当k=2时，合法的排列有{2,1,4,3}、{3,4,1,2}和{4,3,2,1}。

数据范围与提示