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