← 返回题目列表

AtCoder · awc0094_d

D. 选择午餐盒

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

在高桥的公司,他们需要为公司旅行订购便当盒。每个便当都是按照定制订单风格制作的,结合了 3 部分种类:主菜、配菜、甜点。

有 A 主菜选择, B 配菜选择,以及 C 甜点选择。便当由三部分组成(主菜、配菜、甜点)。由于主菜、配菜、甜点都可以独立选择,所以有 便当共有 A \times B \times C 种,任意一种都可以点。

N 员工将参加公司旅游。由于便当是定制的,他们希望为每个人分配一个独特的便当 N 员工,确保没有两名员工收到相同的便当。

这里, 排列的 N 员工之间是有区别的。也就是说,即使集合 N 选择的便当相同,如果哪个员工得到哪个便当的分配不同,则算作不同的分配。

确定有多少种方式将便当分配给 N 员工。

由于答案可能非常大,因此输出除以的余数 10^9 + 7.

约束

  • 1 \leq N \leq 10^6
  • 1 \leq A \leq 10^6
  • 1 \leq B \leq 10^6
  • 1 \leq C \leq 10^6
  • N \leq A \times B \times C (即保证便当总数至少为员工人数)
  • 所有输入均为整数

输入

N A B C

N 代表员工人数, A 代表主菜选择的数量, B 代表配菜选择的数量,以及 C 代表甜点选择的数量,在一行中给出,并用空格分隔。

输出

在单行上输出将相互不同的便当分配给所有便当的方法数量 N 员工,模数 10^9 + 7.


示例输入 1

2 2 1 2

示例输出 1

12

示例输入 2

3 2 2 1

示例输出 2

24

示例输入 3

10 3 3 3

示例输出 3

590793709

示例输入 4

100000 100 100 100

示例输出 4

431436174

示例输入 5

1 1 1 1

示例输出 5

1