  We give a capacity formula for the classical communication over a noisy
quantum channel, when local operations and global permutations allowed in the
encoding and bipartite states preshared between the sender and the receiver.
The two endpoints of this formula are the Holevo capacity (without entanglement
assistance) and the entanglement-assisted capacity (with unlimited entanglement
assistance). What's more, we show that the capacity satisfies the strong
converse property and thus the formula serves as a sharp dividing line between
achievable and unachievable rates of communication. We prove that the
difference between the assisted capacity and the Holevo capacity is upper
bounded by the discord of formation of the preshared state. As examples, we
derive analytically the classical capacity of various quantum channels of
interests. Our result witnesses the power of random permutation in classical
communication, whenever entanglement assistance is available.
