Description

现在有一对幼年兔子，兔子每x个月长大，成年兔子每y个月可以生z对宝宝，假设出生的宝宝每一对雌雄各一只，如果兔子不会死亡，问在第n个月一共有多少对兔子

Format

Input

一行三个整数分别为x,y,z,n(x,y,z<=4,n<=40)

Output

输出第n个月的兔子总数

Samples

1 1 1 3

2

2 3 2 3

1

2 3 3 8

10

Limitation

1s, 1024KiB for each test case.