Substring deletion

Problem Statement

Substring deletion You are given a string S . You have to perform the following operations on it: Pick any two non-overlapping substrings that are exactly the same and delete any one of the substrings. Repeat operation 1 until and unless you are unable to perform that operation. Your task is to obtain the number of different possible strings after performing the operations. Note: Two strings are said to be different when the set of indices selected for the final string generation differs in at least 1 index. 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 in a new line the number of different possible strings that can be generated. Since the answer can be large, print the answer 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". We