---

Problem 929

---

Odd-Run Compositions

A composition of $n$ is a sequence of positive integers which sum to $n$. Such a sequence can be split into runs, where a run is a maximal contiguous subsequence of equal terms.

For example, $2,2,1,1,1,3,2,2$ is a composition of $14$ consisting of four runs:

$2,21,1,132,2$

Let $F(n)$ be the number of compositions of $n$ where every run has odd length.

For example, $F(5)=10$:
$$\begin{array}{rlrlrlrlrl}& 5& & 4,1& & 3,2& & 2,3& & 2,1,2\\ & 2,1,1,1& & 1,4& & 1,3,1& & 1,1,1,2& & 1,1,1,1,1\end{array}$$
Find $F({10}^5)$. Give your answer modulo $1111124111$.

---

奇数长度分段组成

$n$的一个组成是一个和为$n$的正整数序列；这一序列可以进一步分成若干段，每一段是由相等的数构成的最长连续子序列。

例如，$2,2,1,1,1,3,2,2$是$14$的一个组成，可以分成四段：

$2,21,1,132,2$

令$F(n)$为$n$的所有组成中，满足每一段长度都为奇数的组成的数目。

例如，$F(5)=10$：
$$\begin{array}{rlrlrlrlrl}& 5& & 4,1& & 3,2& & 2,3& & 2,1,2\\ & 2,1,1,1& & 1,4& & 1,3,1& & 1,1,1,2& & 1,1,1,1,1\end{array}$$
求$F({10}^5)$，并对$1111124111$取余作为你的答案。

---