---
id: 5900f4c51000cf542c50ffd7
title: 'Задача 344: Гра "Срібний долар"'
challengeType: 1
forumTopicId: 302003
dashedName: problem-344-silver-dollar-game
---

# --description--

One variant of N.G. de Bruijn's silver dollar game can be described as follows:

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

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

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

Переможець - гравець, який забирає срібний долар.

<img class="img-responsive center-block" alt="Гра &quot;Срібний долар&quot;" src="https://cdn.freecodecamp.org/curriculum/project-euler/silver-dollar-game.gif" style="background-color: white; padding: 10px;" />

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

Нехай $W(n, c)$ буде кількістю виграшних конфігурацій у рядку на $n$ квадратів, $c$ монет і один срібний долар.

Дано, що $W(10, 2) = 324$ та $W(100, 10) = 1\\,514\\,7046\\,113\\,500$.

Знайти $W(1\\,000\\,000, 100)$ відповідь до модулю з семіпрієм $1000\\,036\\,000\\,099 (= 1\\,000\\,003 \tстворив 1\\,000\\,000\\,033)$.

# --hints--

`silverDollarGame()` повертає `65579304332`.

```js
assert.strictEqual(silverDollarGame(), 65579304332);
```

# --seed--

## --seed-contents--

```js
function silverDollarGame() {

  return true;
}

silverDollarGame();
```

# --solutions--

```js
// solution required
```
