Кидання камінців по воді

Ви запускаєте каміння по озеру. Щоб камінь підстрибнув на воді, його слід кинути горизонтально, плоскою стороною вниз і паралельно до озера, одночасно надавши йому обертання у момент відпускання. Камінь торкається поверхні води, підстрибує в повітрі на певну відстань, знову торкається води та повторює це, поки не потоне. Обертання допомагає каменю залишатися плоским під час руху, а напрямок залишається незмінним. Траєкторія стрибків каменя незвичайна через нерівності поверхонь самого каменя й озера. Загалом, відстані між стрибками зменшуються, ймовірно, через опір води та повітря. Проте інколи камінь може підстрибнути далі, ніж раніше. Якщо камінь потрапить на латаття, він одразу тоне, ковзаючи по ньому. Кількість стрибків, як правило, досить стабільна (якщо тільки камінь не торкається латаття).

Ваша задача як спеціаліста з інформатики — розробити функцію, яка обчислює ймовірність того, що підкинутий камінь оминатиме всі латаття. Функція приймає два параметри: візерунок латаття ($pads$) у напрямку кидка та максимальну відстань ($maxDist$), яку камінь може подолати після першого удару об воду.

$pads$ подається як рядок, кожен символ якого позначає ділянку озера: $.$ — це відкрита вода, а $\text{X}$ — латаття. Вважайте, що озеро нескінченно продовжується праворуч, постійно повторюючи заданий візерунок. Наприклад, візерунок $.\text{X}.\text{X}..$ відповідає нескінченному озеру .\textbf{X}.\textbf{X}...\textbf{X}.\textbf{X}...\textbf{X}.\textbf{X}.., що простягається праворуч. Ви кидаєте камінь зліва — камінь має приземлитися на першу ділянку (перший символ $pads$, що завжди відкрита вода). Вважайте, що горизонтальний напрямок не змінюється (тобто рух завжди чітко за візерунком латаття).

$maxDist$ задає силу кидка. Для першого стрибка максимальна відстань дорівнює $maxDist$ ділянкам озера. Після кожного стрибка максимальна відстань зменшується на одиницю — для стрибка $N$ (відлік з нуля) максимум буде maxDist - N. Камінь тоне, коли N = maxDist або якщо він потрапляє на латаття. Для стрибка $N$ камінь з рівною ймовірністю може приземлитися на будь-яку цілу відстань від $1$ до maxDist - N (вважаємо, що камінь завжди опиняється у центрі ділянки).

Виведіть імовірність у відсотках (від $0$ до $100$), що камінь жодного разу не торкнеться латаття.