描述

在一个神秘的能源系统中，研究员发现系统每天的能量值都受到前三天能量值的直接影响。具体地讲，第k天的能量值为第k-1天的两倍加上第k-2天的能量值再减去第k-3天的能量值，即：每天的能量值为E(k)=E(k-1)×2+E(k-2)-E(k-3)。

已知初始三天的能量值 a, b, c, 请编写程序计算第 n 天的能量值。

输入格式

四个整数 a, b, c, n

输出格式

一个整数，表示第 n 天的能量值

样例输入

-1 4 3 5

21

数据范围

1 ≤ n ≤ 1000

-1000 ≤ a, b, c, ≤ 1000.

保证所有数据均小于9×10^18