机械计数器是一种常见的辅助工具。一个经典的计数器通常包含一个显示当前计数的区域、一个计数按钮和一个重置按钮。在一个传统的 $N$ 位十进制机械计数器中，复杂的内部机械结构确保按下计数按钮可以将原始计数值精确地增加 1（模 $10^N$）；旋转侧面的重置旋钮会驱动某些数位旋转 1 个位置，旋转足够多次重置旋钮可以将任何初始状态恢复为全零。

计数器的内部触点可能接触不良，从而影响旋转重置旋钮时计数值变化的具体行为。在本题中，假设对于一个理想的计数器，旋转一次重置旋钮时的计数值变化规律如下：

• （下文均考虑前导零）最高位总是旋转 1 个位置，意味着该位数字增加 1（模 10）；
• 如果最高位和从上往下数第 $i$ 位（$2 \le i \le N$）的数字均为 $d$，且从第 2 位到第 $(i-1)$ 位的数字均不大于 $d$，则第 $i$ 位数字旋转 1 个位置，与最高位相同；
• 其他不满足上述条件的数位保持不变。

例如，当计数值为“1151”时，旋转一次重置旋钮会将计数值变为“2251”；当计数值为“9791”时，旋转一次重置旋钮会将计数值变为“0701”。

对于给定的整数 $X$（可能包含前导零），将计数器从初始计数值 $X$ 旋转至全零状态所需的最少重置旋钮旋转次数，定义为 $X$ 的重置旋转次数。对于一个 $N$ 位十进制机械计数器，计算所有 $X \in [L, R]$ 的重置旋转次数之和。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 5\,000$)。 第二行包含两个整数 $L$ 和 $R$（均为 $N$ 位，可能包含前导零；$0 \le L \le R < 10^N$）。

输出格式

输出所有 $X \in [L, R]$ 的重置旋转次数之和。由于总和可能很大，请输出该总和对 $1,000,000,009$ 取模后的结果。

样例

样例输入 1

2
19 23

样例输出 1

51

样例输入 2

6
100084 518118

样例输出 2

9159739

样例输入 3

12
040139021316 234700825190

样例输出 3

771011551