All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given a string s consisting of upper case Latin alphabets, i.e. from 'A' to 'Z'. Your task is to find how many strings t with length equal to that of S, also consisting of upper case Latin alphabet are there satisfying the following conditions:
- String t is lexicographical larger than s
- When you write both s and t in the reverse order, t is still lexicographical larger than s.
Find out number of such strings t. As the answer could be very large, output it modulo 109 + 7
The only line of input contains string s.
Output a single line containing an integer corresponding to the result in modulo 109 + 7.
- 1 ≤ |S| ≤ 105
Input 1: ZAZ Output 1: 25 Input 2: XYZ Output 2: 5
Test #1: To make a valid string t, you can just replace the letter A in S by any other letter, e.g. by replacing 'A' by 'B', we get t = ZBZ. Note that ZBZ is lexicographically larger than ZAZ. Reverse of t (i.e. ZBZ) is also lexicographically larger than reverse of s (i.e. ZAZ).
Test #2: there are 5 valid strings: YYZ, ZYZ, XZZ, YZZ, ZZZ
|Tags||cook74, dynamic-programming, medium, tuananh93|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.