Sum of Pairwise Products in a Digit Sum Constrained Set

Consider a decimal integer \(N = \overline{n_1 n_2 \dots n_m}\) with \(m\) digits. We define \(g(N)=\sum_{i=1}^{m} n_i\). For a given positive integer \(n\), define the set

[ S_n = { x \mid x > 0,; g(x) \le n, ; \text{and every digit in the decimal representation of }x \text{ is nonzero} } ]

We then define

[ f(n)=\sum_{\substack{x,y \in S_n \ x<y}} x \times y \quad (\bmod; 10^6+3). ]

</p>

Your task is to compute \(f(n)\) modulo \(10^6+3\) given \(n\).

Hint: Notice that the double summation can be transformed using the identity:

[ \sum_{x<y} x\times y = \frac{1}{2}\Biggl[\Bigl(\sum_{x\in S_n} x\Bigr)^2-\sum_{x\in S_n}x^2\Biggr]. ]

</p>

inputFormat

The input consists of a single integer \(n\) (\(1 \le n\le \) [constraint as appropriate]) on one line.

outputFormat

Output a single integer which is the value of \(f(n)\) modulo \(10^6+3\).

sample

1

0