問題文

ある日、新しい暦「おたく暦」が採用されることになりました。おたく暦は1年を$M$ヶ月、1ヶ月を$D$日とする暦です。例えば$M$と$D$がそれぞれ2と3であったとき、1年は1月1日、1月2日、1月3日、2月1日、2月2日、2月3日の6日間で構成されます。現在は最適な$M$と$D$が検討されています。

$X$月$Y$日について$X$の数字和と$Y$の数字和が等しいとき、$X$月$Y$日は"SUPER HAPPY DAY"と呼ばれます。ここで数字和とは与えられた整数の各桁の数字が表す数の総和です。例えば4月22日、10月1日、121月2020日は$4=2+2$、$1+0=1$、$1+2+1=2+0+2+0$となりSUPER HAPPY DAYです。一方、4月5日や10月19日、1234月123450日は$4\ne 5$、$1+0\ne 1+9$、$1+2+3+4\ne 1+2+3+4+5+0$となり、SUPER HAPPY DAYではありません。

kamipeipaa君はおたく暦の$M$と$D$が定まったとき，1年間にどれだけSUPER HAPPY DAYがあるか気になっています。kamipeipaa君のために1年間に含まれるSUPER HAPPY DAYの数を$mod$ $1000000009$で求めてください。

入力

$M$ $D$

1行目におたく暦がどのように進むかを表す整数$M$、$D$$(1\le M,D\le {10}^{200})$が空白区切りで与えられる。

出力

1年に含まれるSUPER HAPPY DAYの数を$1000000009$で割った余りを1行で出力してください。改行を忘れないこと。

サンプル

2 3

2

1000000 1000000

581170081

1 1

1