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

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 52
作問者 : testestesttestestest / テスター : PulmnPulmn
0 ProblemId : 1627 / 出題時の順位表
問題文最終更新日: 2018-04-02 19:12:15

問題文

整数$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で実際の値を復元できそうです

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。