题目背景

$CCJ$ 在前往参加 $Universe \ OI$ 的途中。。。

题目描述

有一个神犇 $CCJ$，他在前往参加 $Universe \ OI$ 的途中发现了一个超星系群。在这个超星系群，有着一群生物 $ccj$，他们有着神奇的 $ccj$ 文化，蕴含文史哲艺等多方面内容，具有悠远的历史。他们有自己的文学，自己的科学，当然，还有自己的四叶草和幸运数。在 $ccj$ 文化中，不断进化是生存的必要条件，于是在这个星系群中，有 $k$ 种数字，一个数是幸运数，当且仅当该数中从高位往低位每个数位上的数字单调不降。$CCJ$ 想考验这个超星系群，于是有了一个任务：求由 $k$ 种数字组成的数中 $n$ 位数的幸运数的个数。由于 $ccj$ 文化中缺少超级计算机，你需要帮助他们解决这个简单的问题。

输入格式

第一行一个整数$op$，表示该测试点所属$Subtask$的编号。其中$op=0$表示样例。
第二行两个整数，$n$，$k$，意义如题目描述中所述。

输出格式

一行一个整数，答案$ans$对$10000019$取模。

0
9 9

24310

0
15 24

1257167

提示

数据范围：
$Subtask \ 1$（$10 \%$）：$n \leq 1000$，$k \leq 200$；
$Subtask \ 2$（$40 \%$）：$n \leq 10000$，$k \leq 5000$；
$Subtask \ 3$（$40 \%$）：$n \leq 10000000$，$k \leq 10000000$；
$Subtask \ 4$（$10 \%$）：$n \leq 10^{18}$，$k \leq 10^{18}$；
$Subtask \ 5$（$0 \%$）：$n \leq 10^{100000}$，$k \leq 10^{100000}$。