Background

Will has a mysterious box. It is said that if someone can crack the password on the box, they can foresee the future (for example, know what the official solution of this problem looks like). Would you like to give it a try?

Problem Description

For an $m$-digit decimal integer $N~=~(\overline{n_1 n_2 n_3 \dots n_m})_{10}$, define $g(N)~=~\sum_{i = 1}^{m} n_i$.

Define the set $S_N~=~\{x~|~x~>~0,~g(x)~\leq~N,x~\text{ has no digit equal to } 0 \text{ in its decimal representation}\}$.

Given $n$, compute

$$f(n)~=~\sum_{x \in S_n} \sum_{y \in S_n \land x < y} x~\times~y$$

Output the answer modulo $10^6+3$.

Input Format

One line with a positive integer $n$.

Output Format

One line with one integer, representing the result of the answer modulo $10^6 + 3$.

2

35

Hint

Explanation for Sample Input/Output 1

$S_n={1, 2, 11}$, so $f(N)~=~1 \times 2+1 \times 11+2 \times 11~=~35$.

---

Constraints

For $100\%$ of the testdata, it is guaranteed that $3~\leq~n~\leq~10^{18}$.

Translated by ChatGPT 5