题目描述

在国家 N-兰，人们使用一种以 $n$ 为底的位值计数系统。在这个系统中，自然数使用 $n$ 个数字 $c_1,c_2,\ldots,c_n$ 表示，它们的数值分别为 $1,2,\ldots,n$。

N-兰的科学家们先前有一项重大发现：恰好存在一组严格递增的一位数序列，其中每个数字都恰好出现一次，即序列

现在他们开始研究由两位数组成的序列。更准确地说，他们想知道：有多少个严格递增的两位数序列满足：

• 在整个序列的所有两位数表示中，每个数字都恰好出现两次；
• 对于序列中的每一个两位数，它的高位数字的值都严格小于低位数字的值。

由于问题过于复杂，科学家们先只解决了 $n=3$ 的情形，并发现此时唯一的解是：

请你帮助 N-兰的科学家们，编写程序 seq，求出更大 $n$ 时满足条件的序列个数。

输入格式

输入一行，一个正整数 $n$。

输出格式

输出一行一个整数，表示所求序列个数对 987654321 取模后的结果。

数据范围

• $2 < n < 10^7$
• 在 20% 的测试点中，$n < 13$

样例

输入

3

输出

1