Problem: You’ve just entered a Japanese-style pub, or an izakaya in Japanese, for a drinking party (called nomi-kai) with your dear friends.

Now you are to make orders for glasses of hard and soft drink as requested by the participants. But unfortunately, most staffs in typical izakayas are part-time workers; they are not used to their work so they make mistakes at a certain probability for each order.

You are worrying about such mistakes. Today is a happy day for the participants, the dearest friends of yours.

Your task is to write a program calculating the probability at which the izakaya staff brings correct drinks for the entire orders. Cases in which the staff’s mistakes result in a correct delivery should be counted into the probability, since those cases are acceptable for you.



Input

The input consists of multiple test cases. Each test case begins with a line containing an interger N (1 ≤ N ≤ 8). The integer N indicates the number of kinds of drinks available in the izakaya.

The following N lines specify the probabilities for the drinks in the format shown below.


p11 p12 . . . p1N
p21 p22 . . . p2N
...
pN1 pN2 . . . pNN


Each real number pij indicates the probability where the staff delivers a glass of the drink j for an order of the drink i. It holds that pij ≥ 0 and pi1 + pi2 + . . . + piN = 1 for 1 ≤ i, j ≤ N. At the end of each test case, a line which contains N comes. The i-th integer ni represents the number of orders for the drink i by the participants (0 ≤ ni ≤ 4).

The last test case is followed by a line containing a zero.

Output

For Each test case, print a line containing the test case number (beginning with 1) followed by the natural logarithm of the probability where the staff brings correct drinks for the entire orders. Print the results with eight digits to the right of the decimal point. If the staff cannot bring correct drinks in any case, print “-INFINITY” instead. Use the format of the sample output.

Example

Input

3
0.7 0.1 0.2
0.1 0.8 0.1
0.0 0.0 1.0
4 3 2
8
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125
2 2 2 2 2 2 2 2
2
1 0
1 0
2 2
0


Output

Case 1: -1.89723999
Case 2: -8.14438201
Case 3: -INFINITY

Solution (in CPP):

Solution:
#include <cstdio> 
#include <cstdlib> 
#include <cmath> 
#include <climits> 
#include <cfloat> 
#include <map> 
#include <utility> 
#include <set> 
#include <iostream> 
#include <memory> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <functional> 
#include <sstream> 
#include <complex> 
#include <stack> 
#include <queue> 
#include <cassert>
#include <fstream>
using namespace std; 
#define REP(i,b,n) for(int i=b;i<n;i++) 
#define rep(i,n)      REP(i,0,n) 
#define pb push_back  
#define mp make_pair 
#define ALL(C)   (C).begin(),(C).end() 
template<class T> void vp(T &a,int p){rep(i,p)cout << a[i]<<" ";cout << endl;}  
typedef complex<double>P; 
typedef long long ll; 
typedef unsigned long long ull; 
typedef pair<int,int> pii; 
const int N = 5;
double dp[N][N][N][N][N][N][N][N];
double prob[8][8];

double solve(int n,int now,const vector<int> &ord,const vector<int> &ori,vector<int> &st){
  if (ord.size() == now){
    return 1;
  }
  double &ret=dp[st[0]][st[1]][st[2]][st[3]][st[4]][st[5]][st[6]][st[7]];
  //cout <<"ret " << ret << endl;
  if (ret > -0.5)return ret;
  ret=0;
  rep(i,n){
    if (st[i]+1 > ori[i])continue;
    st[i]++;
    ret+=prob[ord[now]][i]*solve(n,now+1,ord,ori,st);
    st[i]--;
  }
  return ret;
}

int main(){
  int n;
  int tc=1;
  while(cin>>n&&n){
    rep(i,n)rep(j,n)cin>>prob[i][j];
    rep(i0,5)rep(i1,5)rep(i2,5)rep(i3,5)rep(i4,5)rep(i5,5)rep(i6,5)rep(i7,5)
      dp[i0][i1][i2][i3][i4][i5][i6][i7]=-1;
    vector<int> a(8,0),b(8,0);
    vector<int> ord;
    rep(i,n){
      int tmp;
      cin>>tmp;
      vector<int> t(tmp,i);
      a[i]=tmp;
      copy(t.begin(),t.end(),back_inserter(ord));
    }
    double ans = solve(n,0,ord,a,b);
    if (ans == 0)printf("Case %d: -INFINITY\n",tc++);
    else printf("Case %d: %.8lf\n",tc++,log(ans));
  }
  return 0;
}