F - Fito y el Genio

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Si se le dan dos lados de un rectángulo, usted puede calcular su área de manera trivial. ¿Pero usted puede hacer lo contrario? ¿Dado el área de un rectángulo dígame que cantidad de rectángulos diferentes pueden tener esta área siempre que sus lados sean enteros? Dos rectángulos son iguales si sus lados son iguales. Por ejemplo si el área es 6 hay 4 posibilidades 1x6, 2x3, 3x2 y 6x1.
El problema planteado anteriormente es bien sencillo y se puede resolver rápidamente. El problema que tiene que resolver usted es un poco más difícil. Fito tiene un genio en una botella, este le concede un deseo todos los días a Fito. Este lo que hace cada día es decir un número, si este número es positivo entonces el área de la propiedad de Fito se multiplica por este número y en caso de ser negativo se divide por el valor absoluto de este. El área de la propiedad de Fito inicialmente es 1.


Input

La primera línea de la entrada es un entero T (T<=10) que representa la cantidad de casos de prueba de la entrada. Cada caso de prueba comienza con una línea que tiene un entero D (0 < D ≤ 10^6) , que representa la cantidad de días en los que el genio concede un deseo, las próximas D líneas contiene un número G (0< |G|≤ 10^6) ,  que es el numero por el que se multiplica el área de Fito en caso de ser positivo o en que se divide en caso de ser negativo.


Output

Por cada caso de prueba debe de imprimir en una línea “Case X:” donde la X es el número de caso de prueba y luego separado por un espacio la sumatoria de la cantidad diferentes de rectángulos que se pueden obtener que tienen la misma área de la propiedad de Fito después de los D días. Como el numero puede ser bien grande debe de imprimir la respuesta módulo 1000000007(10^9+7).

Sample test(s)

Input
1 5 12 3 -2 5 -6
Output
Case 1: 37

Hints

1er día: Área = 12 -> 6 formas.
2do día: Área = 36-> 9 formas.
3er día: Área = 18 -> 6 formas.
4to día: Área = 90 -> 12 formas.
5to día: Área = 15 ->4 formas.
Por lo que en total (6+9+6+12+4) = 37 formas.