Задача D. Приключения Пиноккио ≡

Условие

Деревянный нос Пиноккио удлиняется на 1 сантиметр каждый раз, когда он говорит неправду. Предприимчивые злодеи Кот и Лиса каждую ночь отпиливают деревянному человечку его нос и продают хозяину харчевни по цене 1 сольдо за 1 сантиметр древесины. Известно, что в первый день Пиноккио соврал a раз, во второй — b, в третий — c, а во все последующие он врал в соответствии с рекуррентной формулой F(d) = F(d − 1) + F(d − 2) − F(d − 3). Сколько сольдо получат Кот и Лиса в d-й день?

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

Единственная строка входного файла содержит четыре натуральных числа, записанных через пробел: a, b, c и d. Гарантируется, что F(d) ≥ 0 для любого d.

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

Выведите одно неотрицательное целое число — ответ на вопрос задачу. Гарантируется, что он не превысит 10¹⁸.

Ограничения

1 ≤ a, b, c, d ≤ 10¹⁵

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

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

Решения, верно работающие при 1 ≤ d ≤ 20, получат не менее 20 баллов.

Решения, верно работающие при 1 ≤ d ≤ 10⁵, получат не менее 60 баллов.

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

В примере в первый день Пиноккио соврал 1 раз, во второй — 3 раза, в третий — 2 раза.

В четвертый день он соврет: 2 + 3 - 1 = 4 раза, в пятый: 4 + 2 - 3 = 3 раза. Значит, Кот и Лиса в пятый день получат 3 сольдо.

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

1 3 2 5

3