　ここでは，文字列において $OMC$ または $MCX$ となっている連続 $3$ 文字の箇所を**ポイント**と呼ぶことにする．すると次のことが確認できる：
- 長さ $4$ の文字列であって，$1$ から $3$ 文字目と $2$ から $4$ 文字目がどちらもポイントとなっているものは $OMCX$ のみである．
- 長さ $5$ の文字列であって，$1$ から $3$ 文字目と $3$ から $5$ 文字目がどちらもポイントとなっているものは存在しない．

文字列において $OMCX$ となっている連続 $4$ 文字の箇所の個数を $x$ とし，$OMCX$ の一部となっていないポイントの個数を $y$ とする．

<details><summary>$x, y$ の例<\/summary>
　ここでは簡単に長さ $20$ の文字列を考える．たとえば文字列が
$$OMCOMCXMCXOOMCXXXOMC$$
の場合，
$$OMC, OMCX, MCX, O, OMCX, X, X, OMC$$
と区切って考えればよく，この文字列における $x, y$ は $x = 2, y = 3$ である．
<\/details>

文字列の長さによる制約から
$$4x + 3y \leq 1110$$
が得られ，ポイントの総数を考えることで
$$2x + y = 554$$
も得られる．ここで得た等式より $y$ は偶数であり，さらに
$$y = (4x + 3y) - 2(2x + y) \leq 1110 - 2 \times 554 = 2$$
が成り立つので，$(x, y)$ としてあり得るものは $(277, 0), (276, 2)$ の $2$ つである．以下場合分けにより議論する．

---

- **Case 1．** $(x, y) = (277, 0)$ のとき： \
　$277 \times 4 = 1108$ なので $OMCX$ の一部となっていない文字の個数は $2$ 個である．そこで $277$ 個の $OMCX$ と $2$ 個の $A$ を並び替えたのち，それぞれの $A$ を $O, M, C, X$ のどれかに置き換える操作の個数を数えればよく，その個数は
$${}\_{279}\mathrm{C}\_{2} \times 4^2 = 620496$$
である．

- **Case 2．** $(x, y) = (276, 2)$ のとき： \
　$276 \times 4 + 2 \times 3 = 1110$ なので，すべての文字がポイントに含まれる．そこで $276$ 個の $OMCX$ と $2$ 個の $A$ を並び替えたのち，それぞれの $A$ を $OMC, MCX$ のいずれかに置き換える操作の個数を数えればよく（置き換え前の $A$ の直前の文字が $O$ であることや，直後の文字が $X$ であることは起こり得ないことに注意），その個数は
$${}\_{278}\mathrm{C}\_{2} \times 2^2 = 154012$$
である．

---

以上の議論より，求める個数は
$$620496 + 154012 = \mathbf{774508}$$
である．
公式解説
https://onlinemathcontest.com/contests/omcb026/editorial/11933
　OMC 君は $1110$ をローマ数字にすると $MCX$ になることに気がついたので，$OMC$ や $MCX$ を含んだ文字列をなんとなく作りたくなってしまいました．\
　そこで OMC 君は，下記の条件をみたすように文字列を作ることにします：
- 文字列の長さは $1110$ であり，使用する文字は $O, M, C, X$ の $4$ 種類である．
- $1 \leq k \leq 1108$ なる整数 $k$ であって，文字列の $k$ 文字目から $k + 2$ 文字目までの $3$ 文字が $OMC$ または $MCX$ になるものがちょうど $554$ 個ある．

OMC 君が作る文字列としてあり得るものは全部で何通りありますか？