题目描述

在上题中，假设战场的图形周长为 $p$，一共有多少种可能的战场？
例如，$p < 8$ 时没有符合要求的战场，$p=8$ 时有 $2$ 种战场：

$p=10$ 时有 $9$ 种战场：

要求输出方案总数模 $987654321$ 的值。

输入格式

输入文件最多包含 $25$ 组测试数据，每个数据仅包含一行，有一个整数 $p$，表示战场的图形周长。$p=0$ 表示输入结束，你的程序不应当处理这一行。

输出格式

对于每组数据，输出仅一行，即满足条件的战场总数除以 $987654321$ 的余数。

7
8
9
10
0

0
2
0
9

数据规模与约定

$100\%$ 的数据满足：$1 \le p \le 10^9$。

提示

湖南省第六届大学生计算机程序设计竞赛

题目来源

鸣谢刘汝佳先生授权使用