旋转排列

时间限制:20s      空间限制:512MB

题目描述


输入格式

输入仅有一行,包含一个整数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}。

提示

没有写明提示


题目来源

没有写明来源