AT_indeednow_2015_finala_f 就職活動

[problemUrl]: https://atcoder.jp/contests/indeednow-finala-open/tasks/indeednow_2015_finala_f 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 $ 点が与えられる。 ### Sample Explanation 1 一人の就職希望者がいるため、就職希望の表は $ 8 $ 通り考えられる。 このうち、どの会社も希望しない場合は就職希望先に就職できなかったものと考える。 したがって、全部で $ 7 $ 通りとなる。 ?