P5257 [JSOI2013] Password

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?

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$.

One line with a positive integer $n$.

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

#### 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