You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

C 国正在进行总统大选。有三位总统候选人分别是小 D，小 O 和小 X。他们分别有 $a,b,c$ 位忠实选民。

这 $a+b+c$ 位选民会排成一队进行投票，有一个初始为空的投票箱，每个人会进行如下操作：

• 如果当前投票箱为空，或者里面的票都是自己支持者的票，那么把自己的票投入；
• 否则，把票箱中任意一张选票撕毁，且不放入自己的选票。

小 L 惊奇的发现最后投完票之后票箱还是空的。

小 L 仔细观察了投票的过程，如果过程当中有 $m$ 次投票箱清空（包括最后一次，但不包括初始），那么他的开心程度为 $m^x$。

小 L 想要知道，在 $\dfrac{(a+b+c)!}{a!b!c!}$ 的排队方式当中，他的开心程度的总和。需要注意的是，如果最终投票箱非空，那么小 L 会不开心，此时他的开心程度为 $0$。

答案对 $10^9+7$ 取模。

输入格式

一行四个正整数表示 $a,b,c,x$。

输出格式

一行一个自然数表示答案。

样例

【样例输入】

1 2 3 1

【样例输出】

110

【样例输入】

2 9 5 2

【样例输出】

0

【样例输入】

9 8 7 6

【样例输出】

399012277

【样例输入】

29 52 29 52

【样例输出】

601894246

【样例输入】

500 499 497 998244353

【样例输出】

973281506

数据范围

对于所有数据，$0\leq a,b,c\leq 500$，$1\leq x\leq 10^9$。