#P18530. Counter Reset Problem

Counter Reset Problem

Counter Reset Problem

机械计数器是一种常见的辅助工具。经典计数器通常有显示当前计数的区域、计数按钮和归零按钮。传统的 NN 位十进制机械计数器通过内部复杂的机械结构,使每次按下计数按钮都恰好将原计数在模 10N10^N 意义下加 11;转动侧面的归零旋钮,则会带动某些数位转动一格。转动足够多次后,可以把任意初始状态恢复为全零。

计数器内部触点可能接触不良,影响转动归零旋钮时数位变化的具体方式。本题假设计数器每转动一次归零旋钮,都按以下规则改变计数。始终保留全部 NN 位,包括前导零,数位从最高位起编号为 1,2,…,N1,2,\ldots,N:

  • 最高位总是转动一格,即该数位在模 1010 意义下加 11。
  • 对第 ii 位(2≤i≤N2\le i\le N),如果最高位和第 ii 位都等于 dd,且第 22 位至第 i−1i-1 位的数位均不大于 dd,则第 ii 位与最高位一起转动一格,也在模 1010 意义下加 11。当 i=2i=2 时,中间没有数位,此条件自然满足。
  • 不满足上述条件的其他数位保持不变。

一次旋转中,各数位是否转动均按本次旋转前的状态判断,并同时变化。例如,1151 转动一次后变成 2251;9791 转动一次后变成 0701。

对一个整数 XX(可能带前导零),将计数器从 XX 转到全零状态所需的最少旋转次数,称为 XX 的清零旋转次数。初始状态已经全零时,该次数为 00。

对于一个 NN 位十进制机械计数器,请计算闭区间 [L,R][L,R] 中所有整数的清零旋转次数之和。

输入格式

第一行包含一个整数 NN,1≤N≤50001\le N\le5000。

第二行包含两个整数 L,RL,R,二者都恰好包含 NN 个十进制数位,可能带前导零。保证 0≤L≤R<10N0\le L\le R<10^N。

输入只有一组数据。

输出格式

输出一行一个非负整数,表示所求总和对 1 000 000 0091\,000\,000\,009 取模后的结果。

样例 1

输入:

2
19 23

输出:

51

样例 2

输入:

6
100084 518118

输出:

9159739

样例 3

输入:

12
040139021316 234700825190

输出:

771011551

以上是三个分别独立的样例,不是同一份输入中的多组数据。