The factorizations of an $n$-cycle of the symmetric group $\Sn$ into $m$ permutations with prescribed cycle types $\a_1,\ldots,\a_m$ describe topological equivalence classes of one pole meromorphic functions on Riemann surfaces. This is one of the motivations for a vast literature on counting such factorizations. Their number, denoted by $c^{(n)}_{\a_1,\ldots,\a_m}$, is also known as a connection coefficient of the center of the algebra of the symmetric group, whose multiplicative structure it describes. The relation to Riemann surfaces induces the definition of a \emph{genus} for factorizations. It turns out that this genus is fully determined by the cycle types $\a_1,\ldots,\a_m$, and that it has a determinant influence on the complexity of computing connection coefficients. In this article, a new formula for $c^{(n)}_{\a_1,\ldots,\a_m}$ is given, that makes this influence of the genus explicit. Moreover, our formula is cancellation--free, thus contrasting with known formulae in terms of characters of the symmetric group. This feature allows us to derive non trivial asymptotic estimates. Our results rely on combining classical methods of the theory of characters of the symmetric group with a combinatorial approach that was first introduced in the much simpler case $m=2$ by Goupil and Schaeffer.