View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You've finished (or at least tried... hopefully) fixing up ButaneBot's OR-sum and Sokoban programs! Now you need to enter ButaneBot's files and update the code. There is a single problem now... to update the code you need to enter ButaneBot's security password, which Butane implemented to stop users from tampering with his files. ButaneBot cannot recall the password, but he remembers that it was a single integer under 10^N. He also remembers that the number is a palindrome. Before you begin coding a brute force check-all-palindromes program to hack into ButaneBot's files, you would like to know how many possible passwords there could be to make sure the program won't run on forever. Since this number may be very big, output the answer modulo 1\,000\,000\,000.

Input Specification

The only line of input will contain a single integer, N (1 \le N \le 10^{25}).

You can assume that 80% of test cases will have (1 \le N \le 100\,000).

Output Specification

The number of palindromes under 10^N.

Sample Input


Sample Output


The palindromes less than or equal to 10^2 are: \displaystyle 1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99


  • 3
    JustinXu  commented on Dec. 8, 2018, 2:16 p.m.

    why am I WA'ing on test case 4

  • -8
    Anix55  commented on Feb. 21, 2017, 8:24 a.m.

    This comment is hidden due to too much negative feedback. Click here to view it.

    • -5
      susheelk  commented on Feb. 21, 2017, 10:08 p.m.

      This comment is hidden due to too much negative feedback. Click here to view it.

  • 0
    kobortor  commented on Dec. 18, 2015, 10:33 a.m.