Vincent là một anh hùng bàn phím thứ thiệt, anh ta có thể gõ với tốc độ gõ phím rất kinh hoàng 1000 WPS. Ở vương quốc của mình anh ta là bá chủ thiên hạ trong bộ môm gõ phím mà không ai địch nổi. Ngoài ra anh ta còn có một skill rất thượng thừa đó là. Tuy nhiên gõ nhanh là vậy nhưng anh ta mắc một lỗi rất nghiệm trọng. Khi anh ta gõ một từ nào đó. Với mỗi ký tự thứ i-th thì ngoài gõ ký tự đó ra anh ta đôi lúc gõ nhầm sang ký tự thứ (i - 1)-th hoặc (i + 1)-th. Với ký tự đầu tiên (O-th) thì anh ta chỉ có thể gõ nhầm sang ký tự 1-th và với ký tự cuối cùng (n - 1)-th thì là ký tự (n - 2)-th. Index bắt đầu từ 0.

Ví dụ:

Anh ta cần gõ từ "aba". tuy nhiên do lỗi kể trên anh ta có thể tạo ra các từ sau: aaa, aab, aba, abb, baa, bab, bba hoặc bbb.

Input:

• Dòng đầu tiên chứ một số nguyên mô tả số lượng testcase T \(( 1 \le T \le 100)\)
• Với mỗi testcase là một chuỗi là từ Vincent cần gõ. Độ dài của từ này ko quá 1000.

Output:

• Dòng duy nhất gồm 1 số nguyên duy nhất X (theo định dạng #Case t: X với t là testcase tương ứng) chỉ số lượng từ khác nhau mà Vincent có thể tạo ra được từ chuỗi ban đầu.
• Do số lượng có thể quá nhiều nên kết quả sẽ được lấy phần dư của 1000000007.

Example:

Input:

3
aba
abcde
aaa

Output:

#Case 1: 8
#Case 2: 108
#Case 3: 1