12. Now use $m$ colors to paint the $n$ sides of a regular $n$-sided polygon, with each side painted one color. Find the number $N$ of II-type patterns of the colored regular $n$-sided polygon.
12. $N=\left\{\begin{array}{ll}\frac{1}{2 n} \sum_{d} \varphi(d) \cdot m^{\frac{n}{d}}+\frac{1}{2} m^{\frac{n+1}{2}}, & n \text { is odd; } \\ \frac{1}{2 n} \sum_{\left.d\right|_{n}} \varphi(d) \cdot m^{\frac{n}{d}}+\frac{1}{4} m^{\frac{n}{2}}(1+m), & n \text { is even. }\end{array}\right.$