/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君の会社では、社員旅行のお弁当を注文することになりました。お弁当は、メインおかず・サイドおかず・デザートの 3 種類のパーツを組み合わせて作るオーダーメイド方式です。
メインおかずには A 種類、サイドおかずには B 種類、デザートには C 種類の選択肢があります。お弁当は（メインおかず、サイドおかず、デザート）の 3 つ組で表されます。メインおかず・サイドおかず・デザートはそれぞれ独立に選べるため、3 つ組の組み合わせとしてお弁当は全部で A \times B \times C 種類存在し、そのどれでも注文可能です。
社員旅行には N 人の社員が参加します。せっかくのオーダーメイドなので、どの 2 人も同じお弁当にならないように、N 人全員にそれぞれ異なるお弁当を 1 つずつ割り当てたいと考えています。
ここで、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 が、スペース区切りで 1 行に与えられる。
出力
N 人全員に互いに異なるお弁当を割り当てる方法の数を 10^9 + 7 で割った余りを 1 行で出力せよ。
入力例 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
Score : 400 pts
Problem Statement
At Takahashi's company, they need to order bento boxes for the company trip. Each bento is made in a custom-order style by combining 3 types of parts: a main dish, a side dish, and a dessert.
There are A choices for the main dish, B choices for the side dish, and C choices for the dessert. A bento is represented as a triplet (main dish, side dish, dessert). Since the main dish, side dish, and dessert can each be chosen independently, there are A \times B \times C types of bento in total, and any of them can be ordered.
N employees will participate in the company trip. Since the bentos are custom-made, they want to assign a distinct bento to each of the N employees so that no two employees receive the same bento.
Here, the N employees are distinguished from each other. That is, even if the set of N chosen bentos is the same, if the assignment of which employee gets which bento differs, it is counted as a different assignment.
Determine how many ways there are to assign bentos to the N employees.
Since the answer can be very large, output the remainder when divided by 10^9 + 7.
Constraints
- 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 (that is, it is guaranteed that the total number of bentos is at least the number of employees)
- All inputs are integers
Input
N A B C
N representing the number of employees, A representing the number of main dish choices, B representing the number of side dish choices, and C representing the number of dessert choices are given on a single line separated by spaces.
Output
Output on a single line the number of ways to assign mutually distinct bentos to all N employees, modulo 10^9 + 7.
Sample Input 1
2 2 1 2
Sample Output 1
12
Sample Input 2
3 2 2 1
Sample Output 2
24
Sample Input 3
10 3 3 3
Sample Output 3
590793709
Sample Input 4
100000 100 100 100
Sample Output 4
431436174
Sample Input 5
1 1 1 1
Sample Output 5
1