No.528 10^9と10^9+7と回文
レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 60
作問者 :
testestest
/ テスター :
Pulmn
タグ : / 解いたユーザー数 60
作問者 :
testestest
/ テスター :
Pulmn
問題文最終更新日: 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、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。