Overview

Given a total of \(M = A \times B \times C\) types of lunch boxes, we need to find the number of ways to assign them to \(N\) distinguishable people without duplication (i.e., the number of permutations), modulo \(10^9+7\).

Analysis

• A lunch box is a triplet of “(Main, Side, Dessert)” chosen independently, so the total number is
  \(M = A \times B \times C\).
• “No two people get the same lunch box” = we need to assign \(N\) distinct items to \(N\) people.
• Furthermore, since “employees are distinguishable,” even if the same \(N\) items are chosen, different assignments of who gets which item count separately.
  In other words, what we need is not a combination but a permutation (injective assignment).

Therefore, the number of ways is [ M \times (M-1) \times (M-2) \times \cdots \times (M-N+1) ] which is a falling factorial (permutation \(P(M,N)\)).

What goes wrong with a naive approach

• \(M\) can be as large as \(10^6 \times 10^6 \times 10^6 = 10^{18}\).
• For example, if we try to compute \(M!\) and then calculate \(\frac{M!}{(M-N)!}\), \(M\) is too large to precompute the factorial (infeasible in both time and memory).
• On the other hand, since \(N \le 10^6\), we only need \(N\) multiplications.

For this reason, the optimal approach is to directly multiply the \(N\) terms of \(P(M,N)\).

(Example) If \(A=2, B=1, C=2\), then \(M=4\). When \(N=3\): [ P(4,3)=4 \times 3 \times 2 = 24 ] ways.

Algorithm

1. Compute \(M = A \times B \times C\).
2. Initialize the answer as \(ans=1\).
3. For \(i=0\) to \(N-1\), perform \(ans \leftarrow ans \times (M-i)\), taking the remainder modulo \(MOD=10^9+7\) each time.
   • In implementation, you can multiply by \((M-i) \bmod MOD\) for each term, so you can start with term = M % MOD and decrement by term -= 1 at each step.
   • If term becomes negative, add term += MOD to maintain \((M-i) \bmod MOD\).

This gives us [ ans \equiv \prod_{i=0}^{N-1} (M-i) \pmod{MOD} ]

Complexity

• Time complexity: \(O(N)\) (\(N\) multiplications)
• Space complexity: \(O(1)\) (only a constant number of variables)

Implementation Notes

• \(M=A\times B\times C\) can be as large as \(10^{18}\), but Python’s int can handle this safely.

• You could keep each term \((M-i)\) as a large integer, but taking MOD each time prevents the values from growing excessively.

• When decrementing term, if it becomes negative, it is safe to restore it to a positive remainder with term += MOD.

  Source Code

import sys

MOD = 1_000_000_007

def main():
    N, A, B, C = map(int, sys.stdin.readline().split())
    M = A * B * C
    term = M % MOD

    ans = 1
    for _ in range(N):
        ans = (ans * term) % MOD
        term -= 1
        if term < 0:
            term += MOD

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.