1246 : 计数器清零问题

Description

机械式计数器是一种常见的辅助工具。一个经典的计数器通常包括指示当前计数的显示区域、一个计数按钮和一个清零按钮。在传统的 \(N\) 位十进制机械式计数器上，复杂的内部机械结构保证了按一次计数按钮会令原先保持的计数在模 \(10^N\) 意义下恰好加 \(1\)；旋转一次侧面的清零旋钮会带动部分数位转动 \(1\) 位，转动足够多次清零旋钮可以将任意初始状态重置为全 \(0\) 的状态。

计数器内部可能接触不良，这会影响旋转清零旋钮时计数变化的具体行为。在本题中，假设对于一个理想的计数器，旋转一次清零旋钮时其计数变化规律为：

• （考虑前导 \(0\) 的，下同）最高位一定旋转 \(1\) 位，即这位数字在模 \(10\) 意义下加 \(1\)；

• 如果最高位和从高往低数第 \(i\) 位（\(2\le i\le N\)）都是 \(d\)，且第 \(2\) 位至第 \((i-1)\) 位的数位都不大于 \(d\)，则第 \(i\) 位与最高位同样旋转 \(1\) 位；

• 其它不满足上述条件的数位均保持不变。

例如，当计数为 1151 时，旋转一次清零旋钮会使得计数变为 2251；当计数为 9791 时，旋转一次清零旋钮会使得计数变为 0701。

对于给定的整数 \(X\)（可能含有前导 \(0\)），称将初始计数为 \(X\) 的计数器旋转至全 \(0\) 状态，需要旋转清零旋钮的最少次数（可能为 \(0\) 次）为 \(X\) 的清零旋转次数。对于一个 \(N\) 位十进制机械式计数器，计算出所有 \(X\in[L,R]\) 的清零旋转次数之和。

Input

输入的第一行包含一个正整数 \(N\)，表示计数器的位数。保证 \(1\le N\le 5000\)。

输入的第二行包含两个可能具有前导 \(0\) 的 \(N\) 位正整数 \(L, R\)，表示求和区间的左右端点。保证 \(0\le L\le R < 10^N\)。

Output

输出 \([L, R]\) 中所有整数的清零旋转次数之和。由于总和可能较大，请输出一个非负整数，表示总和对 \(1,000,000,009\) 取模的结果。

Sample

2
19 23

##CASE##
6
100084 518118

##CASE##
6
068493 205479

##CASE##
12
040139021316 234700825190

51

##CASE##
9159739

##CASE##
3268950

##CASE##
771011551

Hint

【样例解释 #0】

\(19, 20, 21, 22, 23\) 的旋转清零次数分别为 \(9\) 次，\(8\) 次，\(18\) 次，\(8\) 次和 \(8\) 次，故答案为 \(9+8+18+8+8=51\)。

【样例解释 #2】

这个样例，无疑是善良的出题人无私的馈赠。出题人相信，这个美妙的样例，可以给拼搏于 AC 这道题的逐梦之路上的你，提供一个有力的援助。

【提示】

本题中的计数器不是数字电路的计数器。

Source

Author

THU