No.189 SUPER HAPPY DAY

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 76
作問者 : 紙ぺーぱー紙ぺーぱー
1 ProblemId : 493 / 出題時の順位表

問題文

ある日、新しい暦「おたく暦」が採用されることになりました。おたく暦は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 \neq 5$、$1+0 \neq 1+9$、$1+2+3+4 \neq 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行で出力してください。改行を忘れないこと。

サンプル

サンプル1
入力
2 3
出力
2

問題文中に示したように、1/1、1/2、1/3、2/1、2/2、2/3の6日間で1年間が構成され、この中に含まれるSUPER HAPPY DAYは1/1、2/2の2日間です。

サンプル2
入力
1000000 1000000
出力
581170081

1000000009で割ったあまりを出力してください。

サンプル3
入力
1 1
出力
1

毎日がSUPER HAPPY DAYです。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。