Задача 28. Казанова ≡

Условие

...

Зачем делать сложным

То, что проще простого?

Ты — моя женщина,

Я — твой мужчина.

Если надо причину

То это — причина.

...

Илья Кормильцев, "Казанова", 1986 г.

Видеоклип

Женские (F) и мужские (M) последователи Хофштадтера (да, именно так они и называются в математике) рекурсивно определяются следующим образом:

M(0) = 0.

F(0) = 1.

M(n) = n − F(M(n − 1)), n > 0.

F(n) = n − M(F(n − 1)), n > 0.

Определите значение указанной функции. И не делайте сложным то, что проще простого!

Формат входных данных

Единственная строка входного файла содержит запись вида Y(n), где Y — обозначение функции (F или M), а n — неотрицательное целое число, её аргумент.

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

0 ≤ n ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере нужно вычислить F(1).

F(1) = 1 − M(F(1 − 1)) = 1 − M(F(0)) = 1 − M(1). Требуется сначала вычислить M(1).

M(1) = 1 − F(M(1 − 1)) = 1 − F(M(0)) = 1 − F(0) = 1 − 1 = 0.

Тогда F(1) = 1 − M(1) = 1 − 0 = 1.

Примеры тестов

F(1)

1