Японський стиль паб

Ви щойно зайшли до японського пабу, або ізакаї, на вечірку з випивкою (японською - номі-кай) з вашими дорогими друзями.

Тепер вам потрібно зробити замовлення на келихи з міцними та безалкогольними напоями, як того вимагають учасники. Але, на жаль, більшість працівників у типових ізакаях працюють неповний робочий день; вони не звикли до своєї роботи, тому роблять помилки з певною ймовірністю для кожного замовлення.

Ви хвилюєтеся про такі помилки. Сьогодні щасливий день для учасників, ваших найдорожчих друзів.

Ваше завдання - написати програму, яка обчислює ймовірність того, що персонал ізакаї принесе правильні напої для всіх замовлень. Випадки, коли помилки персоналу призводять до правильної доставки, повинні враховуватися в ймовірність, оскільки ці випадки для вас прийнятні.

Вхідні дані

Вхід складається з кількох тестових випадків. Кожен тестовий випадок починається з рядка, що містить ціле число N (1 ≤ N ≤ 8).

Ціле число N вказує на кількість видів напоїв, доступних в ізакаї.

Наступні N рядків визначають ймовірності для напоїв у форматі, показаному нижче.

p_11 p_12 ··· p_1N p_21 p_22 ··· p_2N ··· p_N1 p_N2 ··· p_NN

Кожне дійсне число p_ij вказує на ймовірність того, що персонал доставить келих напою j на замовлення напою i. Вважається, що p_ij ≥ 0 і p_i1 + p_i2 + ··· + p_iN = 1 для 1 ≤ i, j ≤ N. В кінці кожного тестового випадку йде рядок, що містить N. i-те ціле число n_i представляє кількість замовлень на напій i від учасників (0 ≤ n_i ≤ 4).

Останній тестовий випадок завершується рядком, що містить нуль.

Вихідні дані

Для кожного тестового випадку надрукуйте рядок, що містить номер тестового випадку (починаючи з 1), за яким слідує натуральний логарифм ймовірності, що персонал принесе правильні напої для всіх замовлень. Надрукуйте результати з вісьмома цифрами після десяткової коми. Якщо персонал не може принести правильні напої в жодному випадку, надрукуйте "-INFINITY". Використовуйте формат зразкового виводу.