Sum of Primes' Last Four Digits

Given an integer n, find all prime numbers less than n using the Sieve of Eratosthenes algorithm. Let \( S = \sum_{p \text{ prime},\ p < n} p \) be the sum of these primes. Your task is to compute and print the last four digits of \( S \) as a string of length 4. If the sum has fewer than 4 digits, pad it with leading zeros.

inputFormat

The input is provided via standard input (stdin) as a single integer n (\( n \ge 0 \)).

outputFormat

Output via standard output (stdout) a single string representing the last four digits of the sum of all prime numbers less than n. The output must always be 4 characters long (pad with leading zeros if necessary).

10

0017