Number of Battlefields 

In the previous problem, we assume the perimeter of the figure equals to p, how many battlefields are possible? For example, there are no battlefields possible for p < 8, but two for p = 8:

Here are the nine battlefields for p=10:

You're asked to output the number of battlefields modulo 987654321.

Input 

There will be at most 25 test cases, each with a single integer p ( 1$\le$p$\le$109), the perimeter of the battlefield. The input is terminated by p = 0.

Output 

For each test case, print a signle line, the number of battlefields, modulo 987654321.

Sample Input 

8
9
10
0

Sample Output 

0
2
0
9

Problemsetter: Rujia Liu, Special Thanks: Yiming Li, Tanaeem M Moosa & Sohel Hafiz