Bulgaria

Let the two colors be blue and red. We prove first the following

Lemma. Consider $△ABC$ with vertices of both colors. Any coloring of $n$ points inside $△ABC$ is good.

Proof. Without loss of generality assume that $A$ and $B$ are blue points and $C$ is a red point. We proceed by induction on the number $n\ge 0$ of inner points for the triangle. When $n=0$ we draw a segment with end points $A$ and $B$ and we are done. Assume the assertion holds for any triangle with $n=k$ inner points. Consider triangle with $n=k+1$ inner points and let these points be colored in arbitrary manner. If all points are blue then we connect $A$ with $B$ and with all inner points and the condition holds. If there exists a red point $D$, we apply the induction hypothesis for triangles $ABD$, $BCD$ and $ACD$. It is clear that red points from distinct triangles are connected through $D$, and the blue points from distinct triangles are connected through $A$ or $B$. This completes the proof of the lemma. $\square$

Note that for any good coloring all blue points of $M$ are consecutive vertices. Indeed, if this is not the case we have two red points $A$ and $B$, dividing the contour of $M$ into two parts with two blue points $C$ and $D$ in each of these parts. It is clear now that the red path between $A$ and $B$ intersects the blue path between $C$ and $D$, a contradiction.

Let us first count the number of good colorings of the vertexes of $M$. There exist two such colorings with all points having one and the same color. When both colors occur let $k>0$ be the number of blue points. For any $k=1,2,\dots ,2010$ there exist 2011 ways of choosing the group of $k$ consecutive blue points. Therefore we have $2011\cdot 2010+2$ ways of coloring the vertexes of $M$.

We show now that any coloring of the inner points is good. If all vertexes of $M$ have one and the same color (say blue) and all inner point are also blue we connect one vertex with all remaining points. If there exists a red point $B$, then we consider all triangles with one vertex $B$ and sides the sides of $M$. The assertion of the Lemma completes the proof in this case.

Consider coloring of the vertexes of $M$ in which both blue and red points occur. Without loss of generality assume the blue points are $A_1,A_2,\dots ,A_k,k<2011$. Connect $A_1$ with all red points and $A_{k+1}$ with all blue points. Now $M$ is partitioned into triangles and each triangle has vertexes of both colors. Apply the Lemma for each of these triangles. The points having one and the same color from distinct triangles are connected through $A_1$ or $A_{k+1}$ or by the sides of $M$.

Therefore the number of good colorings equals $2^{2011}(2011\cdot 2010+2)$.