Runs (Large)

Count distinct rearrangements of the letters of S whose number of maximal equal-character blocks equals that of S, modulo 1000003.

Hard8CombinatoricsDynamic programmingNo attempts yetTime limit5sMemory limit512 MB

Description

Examples3

Problem

You are given a string $S$ made only of the lowercase letters 'a' to 'z'. A maximal block of equal consecutive characters is called a run. For example, "bookkeeper" has 7 runs. How many distinct rearrangements of $S$ have exactly as many runs as $S$ ?

Two rearrangements $a$ and $b$ are different when some index $i$ satisfies $a[i] \ne b[i]$ .

Input

The first line contains the number of test cases $T$ . Each of the next $T$ lines contains one non-empty string $S$ of lowercase letters.

Limits

$1 \le T \le 100$
$S$ is at least 1 and at most 450000 characters long.
$S$ has at most 100 runs.
The input file is at most 1 megabyte in size.

Output

For each test case print one line of the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of distinct rearrangements of $S$ whose run count equals the run count of $S$ , taken modulo 1000003.