Задача B. Задача из ЕГЭ ≡

Условие

Тимофей готовится к ЕГЭ. Для отработки навыка скорости и точности поиска ответов на задания по теме "Системы счисления" ему часто приходится решать примеры типа "сколько значащих нулей (или единиц) содержит двоичная запись значения выражения 2^a + 2^b − 2^c?" Помогите Тимофею по известным a, b и c узнать ответ на задачу.

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

Первая строка входного файла содержит четыре неотрицательных целых числа, записанных через пробел: a, b, c и d. Числа a, b и c соответствуют показателям степеней двоек в задании. Число d равно либо 0, либо 1 - цифра, количество которых в значении выражения нужно узнать.

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

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

Ограничения

0 ≤ b, c < a ≤ 10¹⁸

0 ≤ d ≤ 1

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

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

Решения, верно работающие при b = с, получат не менее 10 баллов.

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

В примере нужно узнать количество единиц в двоичной записи значения выражения 2⁴ + 2³ − 2². Вычислим: 16 + 8 − 4 = 20. 20₁₀ = 10100₂. Всего две единицы.

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

4 3 2 1

2