题目描述

小明在玩一个养成类游戏，游戏里的每一天都有学习任务，跑步、游泳、击剑，样样都需要。

一年有 $M$ 个月，每个月有 $D$ 天。比如 $M=2,D=3$ 时，一共有 $6$ 天，分别是 $1$ 月 $1$ 日、$1$ 月 $2$ 日、$1$ 月 $3$ 日、$2$ 月 $1$ 日、$2$ 月 $2$ 日、$2$ 月 $3$ 日。天天学习会太疲惫，有些日子会被定义为假日。假日需要满足：月份的数码和等于日期的数码和。这里，数码和是指整数的每个数码的和。

例如：$4$ 月 $22$ 日、$11$ 月 $2$ 日、$121$ 月 $2020$ 日都是假日，因为 $4=2+2$、$1+1=2$、$1+2+1=2+0+2+0$；$4$ 月 $5$ 日、$10$ 月 $12$ 日不是假日，因为 $4 \ne 5$、$1+0 \ne 1+2$。

小明想知道一年里一共有多少个假日，他不会算，来请教学 OI 的你。

输入

一行，两个整数 $M$ 和 $D$。

输出

一个整数，表示一共有多少个假日。答案可能很大，只需要输出 $\bmod 10^9+9$ 的答案。

样例输入 #1

2 3

样例输出 #1

2

样例说明 #1

一共 $6$ 天，假日有 $2$ 天，分别是 $1$ 月 $1$ 日和 $2$ 月 $2$ 日。

样例输入 #2

1 1

样例输出 #2

1

数据范围

$1 \le M,D \le 10^{200}$