思路：数论

几何不等式，每次$+1$操作要让乘积最大，就需要给最小的数$+1$

$\frac{a+b+c}{3}\ge \sqrt[3]{abc}$即$(\frac{a+b+c}{3})^3\ge abc$

等号成立当且仅当$a==b==c$。因此要使乘积最大，三个数要相等，所以执行$+1$操作需要让更小的数$+1$。

假设$a\lt b\lt c$，操作$a$或操作$b$的增加的乘积大小为为$bc$、$ac$，而$bc\gt ac$。因此操作最小的数为最优。

题目内容

小美有三个数字$a,b,c,$他每次操作可以选择一个数字将其加一，最多可以操作$k$次，小美想知道$a×b×c$的最大值是多少？

由于这个数字可能很大，因此你需要输出答案对$10^9+7$取模后的结果。

输入描述

第一行四个正整数$a,b,c,k(1≤a,b,c,k≤10^18)$表示数字和操作次数。

输出描述

输出一个整数表示答案

样例1

输入

1 2 3 1 

输出

12

说明

对1操作一次，三个数字变成[2,2,3],乘积为12

样例2

输入

输出