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