Кидання камінців по воді
Ви кидаєте камінці на озеро. Щоб кинути камінь, ви кидаєте його горизонтально з найплоскішою гранню вниз і паралельно до озера, обертаючи його в момент відпускання. Камінь ковзає по поверхні води, підстрибує в повітрі на певну відстань, потім знову ковзає, повторюючи цей процес, поки не зануриться у воду. Обертання каменя допомагає йому залишатися плоским під час польоту, зберігаючи відносно постійний напрямок. Шаблон, який камінь утворює, підстрибуючи по озеру, досить незвичайний через нерівності поверхонь каменя та озера. В середньому, відстані, на які камінь підстрибує, зменшуються з кожним стрибком, ймовірно, через опір води та повітря. Однак іноді камінь може підстрибнути далі, ніж у попередніх стрибках. Якщо камінь потрапляє на латаття, він одразу тоне після ковзання по ньому. Цікаво, що кількість стрибків каменя здається відносно постійною (якщо він не потрапляє на латаття).
Будучи захопленим комп'ютерним науковцем, ви розробляєте функцію, яка визначає ймовірність того, що камінь, підстрибуючи, уникне всіх латаття. Ваша функція має два вхідні параметри: шаблон латаття (pads) на озері в напрямку, в якому ви кидаєте, і максимальна відстань (maxDist), на яку камінь може підстрибнути після першого удару об воду.
pads подається як рядок. Кожен символ у рядку представляє простір озера: '.' означає відкриту воду, а 'X' — латаття. Припустимо, що озеро нескінченно продовжується вправо, повторюючи шаблон знову і знову. Наприклад, шаблон ".X.X.." відповідає озеру .X.X...X.X...X.X.., яке простягається нескінченно вправо. Ви кидаєте камінь з лівого боку озера на правий і націлюєте його так, щоб він вдарився об перший простір озера (перший символ у pads, який завжди є відкритою водою). Ви також повинні припустити, що горизонтальний напрямок каменя не змінюється (тобто рух каменя завжди вздовж шаблону латаття).
maxDist визначає силу вашого кидка. Для першого стрибка максимальна відстань, на яку камінь може підстрибнути, становить maxDist простору озера. Після кожного стрибка максимальна відстань зменшується на одиницю, що дає максимальну відстань maxDist - N простору для стрибка N (N починається з 0). Камінь занурюється у воду, коли N дорівнює maxDist або коли він потрапляє на латаття. Щоб врахувати непередбачувані шаблони стрибків, припустимо, що камінь має рівні шанси підстрибнути на будь-яку цілу відстань між 1 і maxDist - N включно для стрибка N (для спрощення задачі припустимо, що камінь завжди приземляється в центрі простору).
Ваше значення повернення має бути ймовірністю від 0 до 100, що представляє відсоткову ймовірність того, що камінь не потрапить на жодне латаття.
Вхідні дані
Перший рядок містить рядок pads. Він буде мати від 1 до 50 символів включно і складатиметься лише з символів '.' і 'X'.
Другий рядок містить maxDist. Він буде між 2 і 100 включно.
Вивід
Виведіть одне значення — ймовірність від 0 до 100. Ваша відповідь буде вважатися правильною, якщо вона буде в межах 10^{-9} відносної або абсолютної похибки від правильної відповіді.