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 ≤ p ≤ 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 2 0 9