Problem Statement

Substring deletion You are given a string S . Repeat the following step as many times as possible: Find two substrings that are identical to each other and do not overlap, then erase one of the two copies. Stop once no such pair of matching, non-overlapping substrings remains. Report how many distinct final strings can result from following this process. Note: Two outcomes are treated as different results whenever the sets of surviving character indices differ in at least one position. Input format First line: T denoting the number of test cases. For each test case: First line: A string S . Output format For each test case, print on its own line the number of distinct strings that can result. Since the count can be large, print it modulo 1000000007. Constraints 1 ≤ T ≤ 100 1 ≤ |S| ≤ 10 4 Each character is a lowercase English alphabet (i.e 'a' to 'z'). Example Input: 1 abcc Output: 2 Explanation The original string is "abcc". Consider the two single-character substrings at i