Задачі
Автомат
Автомат
Розглянемо пристрій, який виконує деяку роботу. Крім цього він повинен контролювати свою температуру. Температура не повинна бути занадто високою або занадто низькою. Проте в пристрої вийшов з ладу механізм контролю температури, і тепер пристрій працює наступним чином. Кожну хвилину обирається та виконується один з можливих способів зміни температури. Кожен спосіб вибирається з деякою заданою ймовірністю в залежності від поточної температури.
Вам дані ймовірності змін температури. Вирахуйте ймовірність того, що температура під час роботи пристрою буде знаходитись в заданому інтервалі протягом певного часу.
\InputFile
Перший рядок вхідних даних містить кількість тестів \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{20}). Перший рядок кожного тесту містить чотири цілих числа \textbf{A}, \textbf{B}, \textbf{C}, \textbf{N}, де \textbf{A} -- мінімальна дозволена температура, \textbf{B} -- максимальна дозволена температура, \textbf{C} -- початкова температура, \textbf{N} -- час роботи приладу в хвилинах. \textbf{0} ≤ \textbf{A} ≤ \textbf{B} ≤ \textbf{30}, \textbf{A} ≤ \textbf{C} ≤ \textbf{B}, \textbf{0} ≤ \textbf{N} ≤ \textbf{30}.
Кожен з наступних \textbf{B}--\textbf{A}+\textbf{1} рядків містить \textbf{7} невід'ємних цілих чисел, які в сумі дають \textbf{100} -- ймовірність в процентах зміни температури на \textbf{--4}, \textbf{--3}, \textbf{--2}, \textbf{--1}, \textbf{0}, \textbf{1} та \textbf{2} градуси відповідно. \textbf{K}-й рядок (\textbf{1} ≤ \textbf{K} ≤ \textbf{B}--\textbf{A}+\textbf{1}) описує ймовірності для ситуації, коли поточна температура дорівнює \textbf{A}+\textbf{K}--1.
\OutputFile
Виведіть \textbf{T} рядків вигляду "\textbf{Case} #\textbf{A}: \textbf{B"}, де \textbf{A} -- номер тесту (починаючи з \textbf{1}), \textbf{B} -- шукана ймовірність для даного тесту. Відповідь потрібно вивести без округлення. Гарантується, що відповідь має не більше \textbf{60} десяткових знаків після коми.
Вхідні дані #1
2 1 2 1 2 0 0 0 10 50 40 0 0 0 50 0 0 30 20 3 5 4 5 0 0 0 10 20 30 40 0 0 10 20 30 40 0 0 10 20 30 40 0 0
Вихідні дані #1
Case #1: 0.45 Case #2: 0.59049