logo AlgoBeat OnlineJudge 返回比赛
登录 注册

D. [TopCoder SRM 855] NumReverseHard

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

给定两个正整数 ,考虑所有从 (含两端)的整数。

你可以选择其中任意一些数进行反转操作。反转的含义是将该数的十进制表示逆序写出,并去掉可能存在的前导零。例如,反转 得到 ,反转 得到 (因为 去掉前导零为 )。

操作完成后,将所有数(包括未反转和已反转的)求和。

你需要计算出通过选择反转哪些数,能够得到的最大总和,并将该总和对 取模后输出。

输入格式

第一行包含一个整数
第二行包含一个整数

输出格式

一个整数,表示最大可能的总和对 取模后的结果。

样例

样例 #1

样例输入 #1

21
23

样例输出 #1

75

样例解释 #1

数字集合为 。反转 得到 。总和为 ,这是这三个数能得到的最大总和。


样例 #2

样例输入 #2

12
21

样例输出 #2

489

样例解释 #2

注意反转 后,数字集合中将包含两个 ,它们都会参与求和。


样例 #3

样例输入 #3

97
101

样例输出 #3

495

样例解释 #3

这里最优策略是不反转任何数。


样例 #4

样例输入 #4

123
128

样例输出 #4

3426

样例解释 #4

这里最优策略是反转所有数。


样例 #5

样例输入 #5

89
234

样例输出 #5

67841

样例 #6

样例输入 #6

100000000000000000
100000000000000000

样例输出 #6

300000007

样例解释 #6

唯一的数字是 。最优策略是不反转它(反转后它的值会变为 )。因此最优总和为 ,该值对 取模的结果为

数据范围与提示

数据范围