\(O(N)\) 時間で解く方法について説明します．

本問は次の数え上げに帰着できます．ここまで公式解説と同様です．

• 色 \(0\) の点が \(N_0\) 個，色 \(1\) の点が \(N_1\) 個，色 \(2\) の点が \(N_2\) 個ある．点同士は区別される．
• これらからなる順列（入次数・出次数がすべての点で \(1\) である有向グラフ）であって色 \(0\) の点だけからなるサイクルも，色 \(1\) の点だけからなるサイクルも存在しないものの個数を求めよ．

各単色サイクルをひとつの包除ルールとして包除原理を使います（公式解説では頂点単位で包除ルールを見ているようなのですこし違います）．次ができればよいです：

• \(k\) 個の単色サイクル（色 \(0\) または色 \(1\)）を固定し，それらのサイクルが含まれるような順列を数える．\(k\) の偶奇に応じて \(\pm 1\) の重みで答に加算する．

\(n\) 個の点を固定したとき，それらが \(k\) 個のサイクルになるような順列の個数を \(c_{n,k}\) とします（これは第 1 種スターリング数と呼ばれるものですが，知らなくても解法理解に影響はありません）．包除原理の結果，次のような計算式が得られます：

\[\mathrm{ANS}=\sum_{n_0,n_1,k_0,k_1}(-1)^{k_0+k_1}\binom{N_0}{n_0}\binom{N_1}{n_1}c_{n_0,k_0}c_{n_1,k_1}(N_0+N_1+N_2-n_0-n_1)!\]

二項係数は包除ルールの和集合であるような頂点集合の定め方に対応します（包除ルール同士が頂点を共有する場合は \(0\) 通りなので無視しています）．最後の階乗は包除ルールで選ばれなかった頂点集合を順列にする方法の数え上げです．

ここで有名事実として，次が成り立ちます：

• \(n\geq 2\) ならば \(\sum_k (-1)^k c_{n,k}=0\)

「\(n\geq 2\) ならば偶置換と奇置換の個数は等しい」というような言い方をした方がより有名かもしれません．例えば \(2\) つの点を固定して，その \(2\) 点から出る有向辺の行き先をスワップするとサイクルの個数の偶奇が入れ替わることから証明できます．

したがって，\(n_0,n_1\in\{0,1\}\) に対応する \(4\) つの値の足し引きによって答が計算できます．それぞれは階乗の前計算のもと \(O(1)\) 時間で計算できます．