---

Problem 892

---

Zebra Circles

Consider a circle where $2n$ distinct points have been marked on its circumference.

A cutting $C$ consists of connecting the $2n$ points with $n$ line segments, so that no two line segments intersect, including on their end points. The $n$ line segments then cut the circle into $n+1$ pieces. Each piece is painted either black or white, so that adjacent pieces are opposite colours. Let $d(C)$ be the absolute difference between the numbers of black and white pieces under the cutting $C$.

Let $D(n)$ be the sum of $d(C)$ over all different cuttings $C$. For example, there are five different cuttings with $n=3$.

The upper three cuttings all have $d=0$ because there are two black and two white pieces; the lower two cuttings both have $d=2$ because there are three black and one white pieces. Therefore $D(3)=0+0+0+2+2=4$. You are also given $D(100)\equiv 1172122931(\mathrm{mod}1234567891)$.

Find ${\displaystyle \sum _{n=1}^{{10}^7}D(n)}$. Give your answer modulo $1234567891$.

---

斑马圆

考虑圆周上标记有$2n$个不同的点的圆。

圆上的一个切割$C$是指用$n$条线段连接这$2n$个点，使得任意两条线段不相交且不共端点。这$n$条线段将圆切割成$n+1$块，每块区域被涂成黑色或白色，并满足相邻区域的颜色相反。令$d(C)$为在切割$C$下黑色和白色区域数量的差值的绝对值。

令$D(n)$为所有不同切割$C$的$d(C)$之和。例如，当$n=3$时，有五种不同的切割。

上排三种切割均对应$d=0$，因为它们都有两个黑色区域和两个白色区域；下排两种切割均对应$d=2$，因为它们有三个黑色区域和一个白色区域。因此$D(3)=0+0+0+2+2=4$。已知$D(100)\equiv 1172122931(\mathrm{mod}1234567891)$。

求${\displaystyle \sum _{n=1}^{{10}^7}D(n)}$，并对$1234567891$取余作为你的答案。

---