{"problem":{"name":"G. Singhal and Broken Keyboard (hard version)","description":{"content":"_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from code","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10276G"},"statements":[{"statement_type":"Markdown","content":"_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck._\n\n_The only difference between easy and hard versions is that you have to tell the number of distinct strings in easy version but you have to tell the number of distinct palindromic string in hard version._\n\nSinghal brings a new keyboard consisting of only two English lowercase letters _a_ and _b_. Somehow keyboard is broken and whenever he press a letter to print on screen , it prints the letter twice or thrice.\n\nExample — If he press letter _a_ , then _aa_ or _aaa_ gets printed on the screen with equal probability.\n\nHe wonders that how many distinct palindromic string will be printed on the screen if he press letters of a string $S$ in sequence.\n\nExample — If $S =$ _aba_ , then he first press _a_, then _b_ and at last _a_.\n\nAs the answer can be rather large, print the remainder after dividing it by $1000000007 (10^9 + 7)$.\n\nNote : A palindromic string is a string that reads the same backward as forward, for example strings _z_, _aaa_, _aba_, _abccba_ are palindromes, but strings _codedigger_, _codealittle_, _ab_ are not.\n\nThe first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.\n\nEach query contains a single string $S (1 <= | S | <= 10^5)$ consisting of only two letters _a_ and _b_. $| S |$ is the length of the string.\n\nIt is guaranteed that the total sum of $| S |$ is at most $10^5$.\n\nFor each test from the input print the number of distinct palindrome string modulo $1000000007 (10^9 + 7)$. Print the answers to the tests in the order in which the tests are given in the input.\n\nIn the first query — The strings which can be print on screen if he press _a_ are _aa_ or _aaa_ From these strings all are palindrome also, so number is 2.\n\nIn the second query — The strings which can print on screen are _aabb_ or _aaabb_ or _aabbb_ or _aaabbb_. None of them are palindrome.\n\nIn the last query — The strings which can print on screen are _aaaa_ or _aaaaa_ or _aaaaa_ or _aaaaaa_ . Note that all strings are palindrome and two strings are same , we have to find the distinct palindrome strings.\n\n## Input\n\nThe first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.Each query contains a single string $S (1 <= | S | <= 10^5)$ consisting of only two letters _a_ and _b_. $| S |$ is the length of the string.It is guaranteed that the total sum of $| S |$ is at most $10^5$.\n\n## Output\n\nFor each test from the input print the number of distinct palindrome string modulo $1000000007 (10^9 + 7)$. Print the answers to the tests in the order in which the tests are given in the input.\n\n[samples]\n\n## Note\n\nIn the first query — The strings which can be print on screen if he press _a_ are _aa_ or _aaa_ From these strings all are palindrome also, so number is 2.In the second query — The strings which can print on screen are _aabb_ or _aaabb_ or _aabbb_ or _aaabbb_. None of them are palindrome.In the last query — The strings which can print on screen are _aaaa_ or _aaaaa_ or _aaaaa_ or _aaaaaa_ . Note that all strings are palindrome and two strings are same , we have to find the distinct palindrome strings.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ i \\in \\{1, \\dots, T\\} $, let $ n_i, k_i \\in \\mathbb{Z}^+ $ with $ 1 \\leq n_i, k_i \\leq 10^9 $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10 $  \n2. For each test case $ i $: $ 1 \\leq n_i \\leq 10^9 $, $ 1 \\leq k_i \\leq 10^9 $  \n\n**Objective**  \nFor each test case $ i $, compute the count of positive integers $ x \\leq n_i $ such that:  \n$$\n\\left\\lfloor \\sqrt[k_i]{x} \\right\\rfloor \\mid x\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10276G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}