#include <iostream>
#include <vector>
using namespace std;

long long rec(int p[], int num){
    unsigned long long fin =1;
    long long v =0;
    int x=0;
    int q=0;
    int vp[1000]={0};
    vector<int> myList;
    for (int i=0;i<num;i++)
        vp[i]=p[i];
    for (int k = 0; k < num; k++)
        if(p[k]<0)
            return 0 ;
        else if (p[k]<p[k+1]&& k!=num-1)
            return 0 ;
        else 
            q=q+p[k];
    
    for (int i = 0; i< num; i++){
        for (int j = 0; j < vp[i]; j++){
            x=vp[i]-j;
            for (int k = i+1; k < num; k++){
                p[k]=p[k]-1;
                if (p[k]>=0)
                    x=x+1;
                else{
                    x=x;
                    k=num;
                }
            }
            myList.push_back(x);
        }
        for (int k = 0; k < num; k++)
            p[k]=vp[k];
    }
    for(int s=2;s<=q;s++){
        fin=fin*s;
        // cout << fin << " ";
        for(int f=0;f<myList.size();f++){
            if (fin%myList[f]==0 &&myList[f]!=1){
                fin=fin/myList[f];
                myList.erase(myList.begin()+f);
            }
        }
        for(int f=0;f<myList.size();f++){
            if (myList[f]==1)
                myList.erase(myList.begin()+f);
        }
        v= fin / 1000000009;
        if (v!=0)
            // cout << "fin=" << fin << "v=" << v<<endl;
            fin=fin-v*1000000009;
    }
    // fin = fin % 1000000009;
    return fin;
}
int main(){
    int T, n;
    int p[1000];
    long long a[50]={0};
    cin >> T;
    if (T <= 50){
        for (int i = 1; i <= T; i++){
            cin >> n;
            if (n <= 1000&& n>0){
                for (int u = 0; u < n; u++)
                    cin >> p[u];
                a[i] = rec(p, n);
            }
            else 
                return 0;
        }
        for (int i = 1; i <= T; i++)
            cout << "Case " << i << ": "<< a[i]<< endl;
    }
    else 
        return 0;
}