← 返回题目列表

AtCoder · indeednow_2015_finala_f

F. 找工作

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

問題文

Indeed决定对Susha、Nusha和Kesha这三家公司进行求职调查。
X 我们对求职者进行了调查,看看他们是否愿意在不同的公司工作。3X 对于每一对公司-人员,我们创建了一个表格,列出了每个求职者是否愿意为每家公司工作。
(这样的表是 2^{3X} 有几种可能性。 )
Susha、Nusha 和 Kesha 各有一个最大值 最多 S 人、N 人、K 人可以加入公司。
2^{3X} 在所有可能的方式中,有多少种方式可以让每个人都能找到自己想要的工作?
值 除以 1{,}000{,}000{,}007 求余数。

入力

输入按以下格式给出。

X S N K
  • 1 行包含问题陈述中给出的信息。 4 整数 X, S, N, K (1 \leq S,N,K \leq X \leq 150) 用空格分隔。 如果您对

部分点

针对此问题设置了部分分数。 满足

  • 1 \leq S,N,K \leq X \leq 12 等数据集回答正确,25 点。
  • 如果所有测试用例都回答正确,除了上述之外 75 点。

出力

在一行中输出所需的值。


入力例1

1 1 1 1

出力例1

7

由于有1个求职者,因此求职者表为 8 我可以想到几种方法。
如果您不想在任何公司工作,请考虑您没有在您想要的公司找到工作。
因此,总共 7 就是这样。 直到


入力例2

2 2 1 2

出力例2

48

入力例3

5 4 3 2

出力例3

16384

入力例4

15 12 9 6

出力例4

667797496