Overview

This problem asks us to find the number of ways to select \(N\) lunch boxes from \(A \times B \times C\) types and assign a different one to each of the \(N\) employees.

Analysis

First, let’s consider the total number of lunch boxes. Since there are \(A\) types of main dishes, \(B\) types of side dishes, and \(C\) types of desserts, the total number of lunch box combinations is \(M = A \times B \times C\).

We need to find the number of ways to assign different lunch boxes from these \(M\) types to \(N\) people. - The 1st employee can choose from \(M\) options. - The 2nd employee chooses from the remaining \(M - 1\) options (excluding what the 1st employee chose). - The 3rd employee chooses from \(M - 2\) options. - Repeating this process, the \(N\)-th employee chooses from \(M - N + 1\) options.

Therefore, the answer is the permutation \({}_M P_N\), expressed by the following formula: \(M \times (M - 1) \times (M - 2) \times \dots \times (M - N + 1)\)

An important point to note here is that \(M\) can be as large as \(10^6 \times 10^6 \times 10^6 = 10^{18}\), which is an extremely large value. Therefore, if we try to compute \(\frac{M!}{(M-N)!}\) using factorials, it would require \(M\) iterations of a loop, which would certainly result in TLE (Time Limit Exceeded).

However, the number of people \(N\) to whom we assign lunch boxes is at most \(10^6\). Looking at the formula above, the number of multiplications is exactly \(N\), so the key insight is realizing that a loop of \(N\) iterations can be computed well within the time limit.

Algorithm

1. Compute the total number of lunch boxes \(M = A \times B \times C\), and take the remainder modulo \(10^9 + 7\) in advance.
2. Initialize a variable ans to \(1\).
3. For \(i = 0, 1, 2, \dots, N-1\), repeat the following computation:
   • Multiply ans by \((M - i)\), and assign the remainder modulo \(10^9 + 7\) back to ans.
4. Output the final value of ans.

Complexity

• Time complexity: \(O(N)\) Since we perform multiplications over \(N\) iterations of a loop, the complexity is proportional to \(N\). This results in at most \(10^6\) operations, which is well within the time limit (typically 2 seconds).
• Space complexity: \(O(1)\) Since we do not use arrays or similar structures and only maintain a few variables, the memory usage is constant.

Implementation Notes

• Multiplication of large numbers: Since multiplying \(A, B, C\) together can reach up to \(10^{18}\), when using languages like C++ or Java, you need to use 64-bit integer types (such as long long) to prevent overflow. (In Python, integers are automatically handled as arbitrary-precision integers, so there is no need to worry about types.)

• Negative modulo operations: Since we compute M = (A * B * C) % MOD in the code, M - i may become negative when \(i\) is large. Python’s % operator returns a mathematically correct non-negative remainder even for negative numbers (e.g., -2 % 7 = 5), so the computation works correctly as-is. However, if implementing in C++ or similar languages, you need to adjust to prevent negative values, such as using (M - i % MOD + MOD) % MOD.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    A = int(input_data[1])
    B = int(input_data[2])
    C = int(input_data[3])
    
    MOD = 10**9 + 7
    
    M = (A * B * C) % MOD
    ans = 1
    for i in range(N):
        ans = (ans * (M - i)) % MOD
        
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.