Rainbow Strings

This problem was used in the following GFU competitions:

• GFU 2024 D1 Q6

Define a string to be a rainbow string if every letter in the string is distinct. An empty string is also considered a rainbow string.

Given a string of lowercase letters, compute the number of different subsequences which are rainbow strings. Two subsequences are different if an index is included in one subsequence but not the other, even if the resulting strings are identical.

In the first example, there are 8 subsequences. The only subsequences that aren’t rainbow strings are aa and aab. The remaining 6 subsequences are rainbow strings.

The first input will contain a single integer t that indicates the number of test cases that follow. Each test case will consist of a single string consisting solely of lowercase letters. The length of the string is between 1 and 100,000 (inclusive).

For each test case, print on a single line the number of rainbow sequences, modulo the prime 11,092,019