Last Nine Digits of the Factorial Sum

Let \( S = 1! + 2! + 3! + \dots + 202320232023! \). Find the last nine digits of \( S \), ensuring that the first digit of the answer is nonzero.

Hint: For all \( n \geq 40 \), the term \( n! \) contains at least nine factors of 10 (since \( n! \) is divisible by \( 10^9 \)). Therefore, only the first 39 factorials contribute to the last nine digits, and the problem reduces to computing \( S = \sum_{n=1}^{39} n! \) modulo \( 10^9 \).

inputFormat

No input.

outputFormat

Output a single integer representing the last nine digits of \( S \).

sample

No Input

420940313