Гра з монетами

У грі з монетами горизонтальна смужка розділена на $N$ однакових квадратних клітинок. Спочатку деякі з цих клітинок містять монети, а інші порожні.

Двоє гравців, Дмитро та Іван, по черзі роблять ходи, причому Дмитро ходить першим. Під час кожного ходу гравець може виконати такі дії:

1. Вибрати будь-яку монету, у якої справа є хоча б одна порожня клітинка.

2. Перемістити обрану монету в будь-яку порожню клітинку, що знаходиться правіше.

3. Зсунути всі монети, які розташовані між початковим і новим положенням вибраної монети, рівно на одну клітинку вліво.

Приклад ходу показано на наступних зображеннях:

Монета позначається символом $\text{C}$, а порожня клітинка — символом $\text{.}$. Таким чином, стан смужки можна описати рядком із $N$ символів. Для наведеного прикладу стан смужки до ходу задається рядком $\text{C.CC...C..CC.C}$, а після ходу — $\text{C.C...C..CC.CC}$.

Гравець, який не може зробити хід (тобто всі монети під час його ходу знаходяться поруч із правим краєм смужки), програє гру. Відповідно, виграє той, хто зробив останній хід.

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