No.528 10^9と10^9+7と回文

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 51
作問者 : testestesttestestest / テスター : PulmnPulmn
0 ProblemId : 1627 / 出題時の順位表

問題文

整数$N$が与えられる。1以上$N$以下の整数で、回文数であるものの個数をmod 10^9及びmod 10^9+7で求めなさい。

ただし、回文数とは、"969"、"3223"、"1"のように右から読んでも左から読んでも同じになる数のことである。

入力

N

入力は整数で与えられる
$1\leq N\leq10^{100000}$

出力

1以上$N$以下の整数で、回文数であるものの個数を
mod 10^9で求めたものを1行目に、mod 10^9+7で求めたものを2行目に出力してください。
最後に改行してください。

サンプル

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

1~9はいずれも回分数です

サンプル2
入力
99
出力
18
18

1,2,…,9,11,22,…,99の18個が回分数です

サンプル3
入力
1000000000000000000000000000000
出力
999999998
986000005

10^30以下の回分数はたくさんあるみたいです
余談ですが、このくらいだとChinese Remainder Theoremで実際の値を復元できそうです

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

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