#P6691. [JSOI2019冬令营]小W的数

    ID: 6541 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>难度分类提高构造与建模差分转化组合数学插板法对称性分析贡献法线性代数与代数等比数列求和数论模逆元扩展欧几里得算法快速幂CF2200

[JSOI2019冬令营]小W的数

[JSOI2019冬令营]小W的数

题目描述

小 W 喜欢十进制数位从左到右单调不减的数。

给定整数 xx,求所有位数不超过 xx、且具有上述性质的正整数之和,对 1926081719260817 取模。每个整数使用不含前导零的十进制表示。

例如,x=2x=2 时,需要计算所有一位正整数,以及所有十位数字不大于个位数字的两位数之和。

输入格式

输入一行一个整数 xx。这个数可能很大,以十进制形式给出。

输出格式

输出一行一个整数,表示答案对 1926081719260817 取模后的结果。

样例输入

2

样例输出

1980

数据范围

x≤10300x\le10^{300}。

数据比例 xx 的上界
20%20\% 88
50%50\% 10000001000000
80%80\% 1000000010000000
100%100\% 1030010^{300}