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$.
solutions/s996.md.