#P7435. [2017年杭电多校]Balala Power!

[2017年杭电多校]Balala Power!

Balala Power!

Problem Description

Mr. Tang has nn strings consisting of lowercase English letters. Assign the 2626 letters distinct digits from 00 to 2525, and interpret each string as an integer in base 2626.

Choose one common assignment for all strings to maximize their sum. The resulting numbers must have no leading zeros, except that a number consisting of the single digit 0 is allowed. It is guaranteed that at least one letter does not appear at the beginning of any input string.

Output the maximum sum modulo 109+710^9+7. Maximize the actual integer sum before taking the modulus.

Input

The input contains multiple test cases, ending at EOF. There is no leading test case count.

For each case, the first line contains an integer nn, where 1≤n≤1000001\le n\le100000.

Each of the next nn lines contains a nonempty lowercase string sis_i, with 1≤∣si∣≤1000001\le|s_i|\le100000 and ∑i∣si∣≤106\sum_i|s_i|\le10^6 for this case.

Output

For each case, output one line in the format Case #x: y, where xx is the case number starting from 11, and yy is the maximum sum modulo 109+710^9+7.

样例输入1

1
a
2
aa
bb
3
a
ba
abc

样例输出1

Case #1: 25
Case #2: 1323
Case #3: 18221

Source

2017 Multi-University Training Contest - Team 1