Consider a complete graph \(G\) with \(N\) vertices corresponding to the \(N\) balls, in which the edge between vertex \(i\) and vertex \(j\) has a weight \((A_i^{A_j} + A_j^{A_i}) \bmod M\) (that is, the score obtained when ball \(i\) and ball \(j\) are chosen from the box) for each integer pair \((i, j)\) such that \(1 \leq i \leq j \leq N\).

To come to the point, the answer to this problem is the weight of the maximum spanning tree (the spanning tree with the maximum sum of weights of edges) of graph \(G\). The weight of each edge \((A_i^{A_j} + A_j^{A_i}) \bmod M\) can be computed fast enough with the fast exponentiation. Also, the maximum spanning tree of a graph can be found with Prim’s algorithm of Kruskal’s algorithm, just as the minimum spanning tree.

We describe why the answer equals the weight of the maximum spanning tree of \(G\).

First, for any spanning tree \(T\) of the graph \(G\), there is a procedure to obtain a score equal to the weight of \(T\). This can be achieved by “considering \(T\) as a rooted tree with an arbitrary root and repeating the following operation until ball contains just \(1\) balls.”

• Choose one arbitrary leaf \(v\) of \(T\), and let \(p\) its parent.
• Choose balls \(p\) and \(v\) corresponding to vertices \(p\) and \(v\) from the box, gaining a score equal to the weight of edge \(\lbrace p, v \rbrace\).
• Eat ball \(v\) and return ball \(p\) to the box.
• Also, remove vertex \(v\) (and edge \(\lbrace p, v \rbrace\)) from \(T\).

Conversely, for any procedure against the balls, we can construct a spanning tree of \(G\) whose weight equals the score obtained by the procedure. Specifically, first let \(T\) be a graph whose vertices are the \(N\) vertices of \(G\), and without edge. Then, every time two balls \(i\) and \(j\) are chosen, add an edge \(\lbrace i, j \rbrace\) of \(G\) to \(T\). Finally, \(T\) becomes the desired spanning tree in \(G\).

Therefore, this problem is equivalent to the maximum spanning tree weight problem of the graph \(G\).