给定一个由小写字母 'a'-'z' 组成的字符串 $S$。每一个由相同字符组成的连续子串被称为一个“游程”（run）。例如，"bookkeeper" 有 7 个游程。问 $S$ 的所有排列中，有多少个排列的游程数量与 $S$ 完全相同？

如果两个排列 $a$ 和 $b$ 在某个位置 $i$ 上的字符不同（即 $a[i] \neq b[i]$），则认为它们是不同的排列。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行包含一个非空的小写字母字符串 $S$。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足条件的排列数量，结果对 1000003 取模。

数据范围

$1 \le T \le 100$。 $S$ 的长度至少为 1。

小数据（测试集 1 - 可见；14 分）

$S$ 的长度不超过 100。

大数据（测试集 2 - 隐藏；16 分）

$S$ 的长度不超过 450000。 $S$ 最多有 100 个游程。 输入文件大小不超过 1 兆字节。

样例

样例输入 1

2
aabcd
bookkeeper

样例输出 1

Case #1: 24
Case #2: 7200