Company: Ibm_2dec
Difficulty: medium
Fixing a Damaged Palindromic Message Description Aanya works in a digital archive and is trying to restore a set of corrupted messages. Each message is known to have been a palindrome — a string that reads the same forward and backward. Due to data corruption, some characters in the messages are unreadable and are marked with a question mark (?). Each message consists of lowercase English letters (a-z) and/or '?'. Your task is to help Aanya count: How many different ways can the question marks (?) be replaced with letters so that the message becomes a valid palindrome? Since the number of possibilities can be large, report the answer modulo 10007. Input Format Line contains a non-empty string — a damaged message consisting of lowercase letters and ?. Output Format For each test case, print one line containing the number of valid palindrome completions modulo 10007. Constraints 1 ≤ Total length of string ≤ 1000000 Each string only contains: lowercase letters a-z and '?' characters