UOJ Logo

NOI.AC

1S 512MB

#114. build

统计

【题目描述】

小明收了一块地,要盖一栋房子,我们把土地抽象成一个$N * N$ 的网格, 把楼抽象成由红绿蓝的 $1 * 1 * 1$ 的小立方体堆积起来的建筑物。我们希望求出这样不同楼的方案数。

小明还有一个要求,就是从楼的正面看过去,只能看见一种颜色,我们称作这是优美的楼。

(如下图,左边这个建筑物就是优美的,右边就不是优美的)(从右下方看)

我们会给出每种颜色的小立方体的个数,以及正方形网格的边长,我们要输出所能建成的房子的方案数对 $1e9+7$取模。

注意

  • 1:这里的小立方体显然是不能悬空的。

  • 2:同种颜色的小立方体是完全相同的。

【输入格式】

输入文件 build.in

一行四个整数表示 $R、G、B、N$。分别表示红绿蓝的小立方体个数和网格的边长。

【输出格式】

输出文件 build.out

一行一个整数表示方案数对 $1e9+7$ 取模的结果。

【样例输入】

1 0 1 2 

【样例输出】

4 

【样例数据】

点此下载

【数据范围】

对于 $30$%的数据 $0 \le R,G,B,N \le 10$;

对于 $50$%的数据 $0 \le R,G,B,N \le 25$;

对于 $100$%的数据 $0 \le R,G,B,N \le 50$;