{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eYraglac is expecting to have a child in the near future.\n Being a mathematically-minded person, he would like his child’s\n name to be a palindrome – that is, reads the same when read\n forward and backward. Given a name, he would like to count the\n number of ways he can create a palindromic name by removing\n zero or more letters. For example, given the name “abcdb”, he\n can remove the letters “a” and “c” to get the palindrome “bdb”.\n Of course, the resulting name must not be empty. The answer\n might be very large so you should output the answer modulo\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\, 000\\, 000\\, 007 \u003d 10^9 +\n 7$\u003c/span\u003e.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line contains a single integer \u003cspan class\u003d\"tex2jax_process\"\u003e$T \\leq 10$\u003c/span\u003e giving the number of test\n cases. Each test case consists of a single name with length\n between \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2\\, 000$\u003c/span\u003e inclusive,\n containing only lowercase letters.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eFor each test case, output a single line containing the\n answer modulo \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\, 000\\, 000\\,\n 007$\u003c/span\u003e.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\nbob\na\naa\naaa\nabcdb\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1\n3\n7\n8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}