\(N\) 個のボールに対応する \(N\) 個の頂点を持ち、\(1 \leq i \lt j \leq N\) を満たすすべての整数の組 \((i, j)\) について、頂点 \(i\) と頂点 \(j\) の間に重みが \((A_i^{A_j} + A_j^{A_i}) \bmod M\) （すなわち、ボール \(i\) とボール \(j\) を箱から取り出したときに得られる得点）の無向辺を張って得られる完全グラフ \(G\) を考えます。

結論を述べると、本問題の答えはグラフ \(G\) の最大全域木（辺の重みの和が最大の全域木）の重みです。 各辺の重み \((A_i^{A_j} + A_j^{A_i}) \bmod M\) は、繰り返し二乗法によって十分高速に求められます。また、グラフの最大全域木は、最小全域木と同様に Prim 法や Kruskal 法などのアルゴリズムによって十分高速に求めることができます。

以下、本問題の答えがグラフ \(G\) の最大全域木の重みである理由を述べます。

まず、グラフ \(G\) の任意の全域木 \(T\) に対し、\(T\) の重みに等しい得点を獲得する手順が存在します。 これは「 \(T\) を適当な頂点を根とした根付き木と考え、箱に残ったボールが \(1\) 個になるまで下記の操作を繰り返す」という手順です。

• \(T\) の葉 \(v\) を任意に \(1\) つ選び、その親を頂点 \(p\) とおく。
• 頂点 \(p, v\) に対応するボール \(p, v\) を箱から取り出し、辺 \(\lbrace p, v \rbrace\) の重みに等しい得点を獲得する。
• ボール \(v\) を食べて、ボール \(p\) を箱に戻す。
• それに対応して、\(T\) から頂点 \(v\) （および辺 \(\lbrace p, v \rbrace\) ）を削除する。

反対に、ボールに対する任意の手順に対して、それによって獲得できる得点と同じ重みを持つ \(G\) の全域木を構築できます。 具体的には、まず \(T\) を、\(G\) の \(N\) 個の頂点を頂点として持ち、辺を持たないグラフとします。 そして以後、\(2\) つのボール \(i, j\) を箱から取り出すたびに、\(G\) の辺 \(\lbrace i, j \rbrace\) を \(T\) に加えていくことで、最終的に \(T\) は \(G\) における所望の全域木となります。

以上より、本問題はグラフ \(G\) の最大全域木の重みを求める問題と等価です。