No.528 10^9, 10^9+7, and Palindromes
タグ : / 解いたユーザー数 65
作問者 :
testestest
/ テスター :
Pulmn
Problem Statement
You are given an integer $N$. Find the number of palindromic numbers among the integers between 1 and $N$, inclusive, modulo 10^9 and modulo 10^9+7.
Here, a palindromic number is a number that reads the same from right to left and from left to right, such as "969", "3223", and "1".
Input
N
The input is given as an integer.
$1\leq N\leq10^{100000}$
Output
For the number of palindromic numbers among the integers between 1 and $N$, inclusive,
print the value modulo 10^9 on the first line and the value modulo 10^9+7 on the second line.
Print a newline at the end.
Sample
Sample 1
Input
9
Output
9 9
All of 1 to 9 are palindromic numbers.
Sample 2
Input
99
Output
18 18
The 18 numbers 1,2,…,9,11,22,…,99 are palindromic numbers.
Sample 3
Input
1000000000000000000000000000000
Output
999999998 986000005
There seem to be a lot of palindromic numbers not exceeding 10^30.
As an aside, at about this size it seems possible to recover the actual value using the Chinese Remainder Theorem.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。