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 <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
vector<int> v;
vector<int> cnt;
int N, M, G;
double p[8][8] = {};
double memo[390626];
int pow5[8];
double dfs(const int S){
  if(memo[S] >= 0) return memo[S];
  if(S == G) return memo[S] = 1.0;
  vector<int> cur(N);
  int idx = 0;
  int TMPS = S;
  REP(i, N){
    cur[i] = TMPS % 5;
    idx += cur[i];
    TMPS /= 5;
  }
  if(idx == v.size()) return memo[S] = 0.0;
  int u = v[idx];
  memo[S] = 0;
  REP(v, N){
    if(cur[v] + 1 > cnt[v]) continue;
    int NS = S + pow5[v];
    memo[S] += p[u][v] * dfs(NS);
  }
  return memo[S];
}

int main(){
  pow5[0] = 1;
  for(int i = 1; i < 8; i++) pow5[i] = 5 * pow5[i - 1];
  int CASENUM = 1;
  while(cin >> N && N){
    printf("Case %d: ", CASENUM++);
    v.clear();
    cnt = vector<int>(N);
    G = 0;
    REP(i, 390626) memo[i] = -1.0;

    REP(i, N) REP(j, N) cin >> p[i][j];

    REP(i, N){
      int t; cin >> t;
      cnt[i] = t;
      REP(j, t) v.push_back(i);
      G += t * pow5[i];
    }

    M = v.size();

    double ans = dfs(0);
    if(ans == 0.0) cout << "-INFINITY" << endl;
    else printf("%.8lf\n", log(ans));
  }
  return 0;
}