New Year and Original Order

题意翻译

给$n<=10^{700}$,问1到n中每个数在各数位排序后得到的数的和。答案膜1e9+7。 Translated by @远航之曲

题目描述

Let $ S(n) $ denote the number that represents the digits of $ n $ in sorted order. For example, $ S(1)=1,S(5)=5,S(50394)=3459,S(353535)=333555 $ . Given a number $ X $ , compute ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF908G/86189a2fc1d31a8560e966bada6dfd32afab65e2.png) modulo $ 10^{9}+7 $ .

输入输出格式

输入格式


The first line of input will contain the integer $ X $ ( $ 1<=X<=10^{700} $ ).

输出格式


Print a single integer, the answer to the question.

输入输出样例

输入样例 #1

21

输出样例 #1

195

输入样例 #2

345342

输出样例 #2

390548434

说明

The first few values of $ S $ are $ 1,2,3,4,5,6,7,8,9,1,11,12,13,14,15,16,17,18,19,2,12 $ . The sum of these values is $ 195 $ .