---

Problem 976

---

XO Game

Two players X and O play a game with $k$ strips of squares of lengths $n_1,\dots,n_k$, originally all blank.

Starting with X, they make moves in turn. At X’s turn, X draws an “X” symbol; at O’s turn, O draws an “O” symbol.
The symbol must be drawn in one blank square with either red or blue pen, subject to the following restrictions:

1. two symbols in adjacent squares on one strip must be different symbols and must have different colour;
2. if there is at least one blank strip, then one must draw on a blank strip.

Whoever does not have a valid move loses the game.

Let $P(K, N)$ be the number of tuples $(n_1,\dots,n_k)$ such that $1 \leq k \leq K$, $1\leq n_1\leq\cdots\leq n_k\leq N$ and that X has a winning strategy to the corresponding game.

For example, $P(2, 4)=7$ and $P(5, 10) = 901$.

Find $P(10^7, 10^7)\bmod 1234567891$.

---

XO游戏

两名玩家X和O用$k$条长度分别为$n_1,\dots,n_k$的方格条进行游戏，所有方格初始均为空白。

由X先手，双方轮流行动。轮到X时，X画一个”X”符号；轮到O时，O画一个”O”符号。
符号必须用红色或蓝色的笔画在某个空白方格中，并遵循以下条件：

1. 同一条方格条上相邻方格中的两个符号必须是不同的符号且必须是不同的颜色；
2. 如果存在至少一条完全空白的方格条，则符号必须画在某一条空白的方格条上。

首先无法行动的玩家将输掉游戏。

记$P(K, N)$为满足以下条件的元组$(n_1,\dots,n_k)$的数量：$1 \leq k \leq K$，$1\leq n_1\leq\cdots\leq n_k\leq N$，且X在对应的游戏中有必胜策略。

例如，$P(2, 4)=7$，$P(5, 10) = 901$。

求$P(10^7, 10^7)\bmod 1234567891$。

---