---

Problem 996

---

Overtakes

There are $n$ tennis players on a leader board, from rank $1$ (highest) to rank $n$ (lowest).

Every day, a match is held between a pair of players with adjacent ranks. When the higher rank player wins, nothing happens; otherwise, their ranks are exchanged, and we call that match an overtake by the winning player.

After $k$ days, the players find that all of them are back to their initial ranks. They then count the number of overtakes by each player.

Here is an example with $3$ players, named $A, B, C$ from highest to lowest initial rank.

Match	Winner	Loser	Rank $1, 2, 3$ after match	Overtake counts
				$A$	$B$	$C$
$1*$	$C$	$B$	$A, C, B$	$0$	$0$	$1$
$2$	$C$	$B$	$A, C, B$	$0$	$0$	$1$
$3*$	$C$	$A$	$C, A, B$	$0$	$0$	$2$
$4$	$A$	$B$	$C, A, B$	$0$	$0$	$2$
$5*$	$A$	$C$	$A, C, B$	$1$	$0$	$2$
$6*$	$B$	$C$	$A, B, C$	$1$	$1$	$2$

The matches marked with $*$ are overtakes.

After $6$ days, all players are back to initial ranks with overtake counts $1, 1, 2$.

Let $F(n, k)$ be the number of possible $n$-tuples of overtake counts after $k$ days, assuming that all players are back to initial ranks.

You are given $F(3, 4) = 8$ and $F(12, 34) = 2457178250$.

Find $F(123, 4567891) \bmod 1234567891$.

---

反超

排行榜上现有$n$名网球选手，排名从第$1$（最高）到第$n$（最低）。

每一天，恰有两位排名相邻的选手之间会进行一场比赛。当排名较高的选手获胜时，无事发生；否则，两人的排名互换，并称这场比赛为获胜选手的一次反超。

经过$k$天后，选手们发现所有人都回到了最初的排名；此时他们数了一下每位选手的反超次数。

如下例子中有$3$名选手，按初始排名从高到低分别称为$A, B, C$。

比赛	胜方	败方	比赛后排名 $1, 2, 3$名	反超次数
				$A$	$B$	$C$
$1*$	$C$	$B$	$A, C, B$	$0$	$0$	$1$
$2$	$C$	$B$	$A, C, B$	$0$	$0$	$1$
$3*$	$C$	$A$	$C, A, B$	$0$	$0$	$2$
$4$	$A$	$B$	$C, A, B$	$0$	$0$	$2$
$5*$	$A$	$C$	$A, C, B$	$1$	$0$	$2$
$6*$	$B$	$C$	$A, B, C$	$1$	$1$	$2$

标有$*$的比赛表示反超。

$6$天后，所有选手都回到了初始排名，反超次数分别为$1, 1, 2$。

记$F(n, k)$为$k$天后所有选手都回到初始排名的情况下，所有可能的反超次数$n$元组的数目。

已知$F(3, 4) = 8$，$F(12, 34) = 2457178250$。

求$F(123, 4567891) \bmod 1234567891$。

---