题目描述

一个$\red{n}$的全排列$\red{A[i]}$是单峰的，当且仅当存在某个$\red{x}$使得$\red{A[1]<A[2]<...<A[x]>A[x+1]>...> A[n]}$。例如，对于$\red{9}$的全排列，$\red{125798643}$是一个单峰排列，$\red{123456789}$也是一个单峰排列，但$\red{356298741}$就不是。试求$\red{n}$的单峰全排列的个数。

输入格式

一个整数$\red{n}$。

输出格式

输出$\red{n}$的全排列中单峰排列的个数。 由于这个数可能很大，因此你只需要输出它$\red{mod 1234567}$的值。

样例

输入样例

3

输出样例

4

提示

$\red{n<=2 000 000 000}$