{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" \n \u003cp\u003eGiven a string, calculate the number of subsequences that are palindrome. A palindrome is a sequence of characters that reads the same backward or forward. For example, in the string “aba”, there are 7 subsequences \"a\", \"b\", \"a\", \"ab\", \"aa\", \"ba\", \"aba\". Only \"a\", \"b\", \"a\", \"aa\", \"aba\" are palindrome. Two subsequences that contain characters from different positions are considered different.\u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp\u003eThe first line of input contains a single integer T specifying the number of test cases. \u0026nbsp;In each test case, there is only one line containing a string.\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp\u003eFor each test case, output a line containing \"Case #X: Y\", where X is the test case number starting from 1, followed by one integer Y indicating the number of palindrome subsequences. Output the answer modulo 100007.\u003c/p\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \n \u003cpre\u003e5\r\naba\r\nabcbaddabcba\r\n12111112351121\r\nccccccc\r\nfdadfa\r\n\u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003eCase #1: 5\r\nCase #2: 277\r\nCase #3: 1333\r\nCase #4: 127\r\nCase #5: 17\u003c/pre\u003e \n "}}]}