概要

お弁当の総数 \(M = A \times B \times C\) 種類から、区別される \(N\) 人に重複なく割り当てる方法数（順列数）を、\(10^9+7\) で割った余りで求めます。

考察

• お弁当は「(メイン, サイド, デザート)」の \(3\) つ組で、独立に選べるので総数は
  \(M = A \times B \times C\) です。
• 「どの2人も同じお弁当にならない」＝ \(N\) 人に 異なる \(N\) 個 を割り当てる必要があります。
• さらに「社員は区別する」ので、同じ \(N\) 個を選んでも誰にどれを渡すかが違えば別カウントです。
  つまり、求めるのは組合せではなく 順列（注入的な割り当て）です。

よって方法数は [ M \times (M-1) \times (M-2) \times \cdots \times (M-N+1) ] という 降順の積（順列 \(P(M,N)\)） になります。

素朴にやると何が困るか

• \(M\) は最大で \(10^6 \times 10^6 \times 10^6 = 10^{18}\) になり得ます。
• 例えば \(M!\) を作って \(\frac{M!}{(M-N)!}\) の形で計算しようとしても、\(M\) が大きすぎて階乗の前計算が不可能です（時間・メモリともに無理）。
• 一方で \(N \le 10^6\) なので、必要な掛け算は \(N\) 回だけ で十分です。

このため、\(P(M,N)\) をそのまま \(N\) 項だけ掛けていくのが最適です。

（例）\(A=2,B=1,C=2\) なら \(M=4\)。\(N=3\) のとき
[ P(4,3)=4 \times 3 \times 2 = 24 ] 通り。

アルゴリズム

1. \(M = A \times B \times C\) を計算する。
2. 答えを \(ans=1\) とする。
3. \(i=0\) から \(N-1\) まで順に、\(ans \leftarrow ans \times (M-i)\) を行い、その都度 \(MOD=10^9+7\) で割った余りを取る。
   • 実装では各項を \((M-i) \bmod MOD\) にして掛ければよいので、term = M % MOD から始めて term -= 1 していく形で計算できる。
   • term が負になったら term += MOD して \((M-i) \bmod MOD\) を保つ。

これで [ ans \equiv \prod_{i=0}^{N-1} (M-i) \pmod{MOD} ] が得られます。

計算量

• 時間計算量: \(O(N)\)（掛け算を \(N\) 回）
• 空間計算量: \(O(1)\)（定数個の変数のみ）

実装のポイント

• \(M=A\times B\times C\) は最大 \(10^{18}\) ですが、Python の int なら安全に扱えます。

• 各項は \((M-i)\) をそのまま巨大整数で持ち続けてもよいですが、毎回 MOD を取ることで値の肥大化を防げます。

• term を減らしていくとき、負になった場合は term += MOD して正の剰余に戻すのが安全です。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。