Problem Statement

One day, it was decided that a new calendar, the "Otaku Calendar", would be adopted. In the Otaku Calendar, one year consists of $M$ months and one month consists of $D$ days. For example, when $M$ and $D$ are 2 and 3 respectively, one year consists of the 6 days: January 1, January 2, January 3, February 1, February 2, and February 3. Currently, the optimal $M$ and $D$ are under consideration.

For month $X$, day $Y$, if the digit sum of $X$ and the digit sum of $Y$ are equal, month $X$, day $Y$ is called a "SUPER HAPPY DAY". Here, the digit sum is the sum of the numbers represented by the digits of a given integer. For example, month 4 day 22, month 10 day 1, and month 121 day 2020 are SUPER HAPPY DAYs, since $4 = 2+ 2$, $1+0=1$, and $1+2+1=2+0+2+0$. On the other hand, month 4 day 5, month 10 day 19, and month 1234 day 123450 are not SUPER HAPPY DAYs, since $4 \neq 5$, $1+0 \neq 1+9$, and $1+2+3+4 \neq 1+2+3+4+5+0$.

Kamipeipaa wonders how many SUPER HAPPY DAYs there are in one year once $M$ and $D$ of the Otaku Calendar are determined. For Kamipeipaa, find the number of SUPER HAPPY DAYs in one year, modulo $mod$ $1000000009$.

Input

$M$ $D$

On the first line, the integers $M$ and $D$$(1 \le M, D \le 10^{200})$, which represent how the Otaku Calendar proceeds, are given separated by a space.

Output

Output on one line the remainder when the number of SUPER HAPPY DAYs in one year is divided by $1000000009$. Do not forget the newline.

Sample

2 3

2

1000000 1000000

581170081

1 1

1