{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eCounting strings has been an interesting thing for Mr. Frog since he was 6 years old. Whenever given a string s, Mr. Frog may tell you how many strings in the same length are lexicographically smaller than or equal to s. But now, as an university student, elementary questions may not arouse Mr. Frog’s interest, so a harder question appeared.\u003cbr\u003e\u003cbr\u003eWe call a string t representative string if t is the lexicographically smallest string in an equivalence class of strings under rotation. Given s, Mr. Frog wants to know how many representative strings t, in the same length as s, are lexicographically smaller than or equal to s. In order to be a magician, you may want to solve this challenge quickly to attract Mr. Frog’s attention.\u003cbr\u003e\u003cbr\u003eOnly those t consisting of lowercase letters should be considered.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains only one integer $T (T\\leq 30)$, which indicates the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, there is only one line describing the given string $s (1\\leq |s| \\leq 100$), s consists of lowercase letters."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line “Case #x: y”, where x is the case number (starting from 1) and y is the number of representative strings to this question modulo 1000000007"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e2\r\nbb\r\nbab\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 27\r\nCase #2: 651\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eFor the first sample, the representative strings smaller than or equal to bb are aa, ab, …, az, bb.\u003cbr\u003e"}}]}