OMCB026(G)

点数: 300

Writer: Shota_1110

　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 君が作る文字列としてあり得るものは全部で何通りありますか？