题目背景

Will 有一个神秘盒，传说只要有人能解开神秘盒上的密码，就可以预知未来（比如知道这道题的标程是怎样的），你愿意来尝试一下么？

题目描述

对于一个 $m$ 位的十进制整数 $N~=~(\overline{n_1 n_2 n_3 \dots n_m})_{10}$，定义 $g(N)~=~\sum_{i = 1}^{m} n_i$。

定义集合 $S_N~=~\{x~|~x~>~0,~g(x)~\leq~N,x~\text{的十进制表示中任意位不为} 0\}$。

给定 $n$，求

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

答案对 $10^6+3$ 取模。

输入格式

一行一个正整数 $n$。

输出格式

一行一个整数代表答案对 $10^6 + 3$ 取模的结果。

2

35

提示

样例输入输出 1 解释

$S_n={1, 2, 11}$，故 $f(N)~=~1 \times 2+1 \times 11+2 \times 11~=~35$。

---

数据规模与约定

对于 $100\%$ 的数据，保证 $3~\leq~n~\leq~10^{18}$。