F - 就職活動 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed 社では、す社、ぬ社、け社の三社への就職活動について調査をすることにした。
X 人の就職希望者にす、ぬ、け各社に就職したいかアンケートをとり、3X 組の会社と人のペアに対し、各就職希望者がす、ぬ、け各社に就職したいかどうかを集計した表を作成した。
(このような表は 2^{3X} 通り考えられる。)
す社、ぬ社、け社にはそれぞれ最大で 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

一人の就職希望者がいるため、就職希望の表は 8 通り考えられる。
このうち、どの会社も希望しない場合は就職希望先に就職できなかったものと考える。
したがって、全部で 7 通りとなる。

入力例2

2 2 1 2

出力例2

48

入力例3

5 4 3 2

出力例3

16384

入力例4

15 12 9 6

出力例4

667797496