一个n的全排列a[i]是单峰的，当且仅当存在某个x使得a[1]a[x+1]>...>a[n-1]>a[n]. 例如，对于9的全排列，123679854是一个单峰排列，123456789也是一个单峰排列，但143298765不是. 现在的任务是求出n的全排列中单峰排列的种数k. 当然k可能很大，你只需要求出k mod 1234567的值.

输入一个数n.

输出一个数：k mod 1234567 的值，k即n的全排列中单峰排列的种数.

3

4

附中模拟