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, 2\quad 1, 1, 1\quad 3 \quad 2, 2$

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

For example, $F(5)=10$:
$$
\begin{aligned}
& 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{aligned}
$$
Find $F(10^5)$. Give your answer modulo $1111124111$.

奇数长度分段组成

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

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

$2, 2\quad 1, 1, 1\quad 3 \quad 2, 2$

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

例如，$F(5)=10$：
$$
\begin{aligned}
& 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{aligned}
$$
求$F(10^5)$，并对$1111124111$取余作为你的答案。