Counting n-digit Squares Ending with 987654321

You are given a positive integer n. Your task is to count how many n-digit numbers x satisfy the property that the last 9 digits of x^2 equal 987654321. In other words, if we define M = 10^9 and r = 987654321, you need to count the numbers x such that:

\( x^2 \equiv 987654321 \; (\bmod\; 10^9) \)

Note that the condition x^2 mod 10^9 = 987654321 is a quadratic congruence modulo 10^9. Since 10^9 = 2^9 \times 5^9, one can show (using Hensel's lemma and the Chinese Remainder Theorem) that if a solution exists, there are exactly 8 residue classes modulo 10^9 satisfying the equation.

The overall approach is as follows:

• Find all 8 solutions s in the range [0, 10^9-1] such that \( s^2 \equiv 987654321 \; (\bmod\; 10^9) \).
• Let the range of n-digit numbers be \( [10^{n-1}, 10^n - 1] \). For each residue s, count how many numbers in that range are congruent to s modulo 10^9.
• Output the sum of these counts.

Input Format: A single integer n.

Output Format: Output one integer – the total count of n-digit numbers whose square ends with 987654321.

Note: It is guaranteed that if a solution exists for the congruence \( x^2 \equiv 987654321 \; (\bmod\; 10^9) \), then there are exactly 8 residue classes modulo 10^9 that satisfy it. Your solution must use this fact to count the numbers efficiently.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10^5), which denotes the number of digits.

outputFormat

Output a single integer – the number of n-digit numbers whose square ends with 987654321.

sample

1

0