Problem 973

Random Dealings

A game is played with $n$ cards.
At the start the cards are dealt out onto a table to get $n$ piles of size one.

Each round proceeds as follows:

Select a pile at random and pick it up.
Randomly choose a pile from the table and add the top card of the picked-up pile to it.
Redistribute any remaining cards from the picked-up pile by dealing them into new single-card piles.

The game ends when all cards are in a single pile.

At the end of each round a score is obtained by bitwise-XORing the size of each pile. The score is summed across the rounds. Let $X(n)$ be the expected total score at the end of the game.

You are given $X(2) = 2$, $X(4) = 14$ and $X(10) = 1418$.

Find $X(10^4)$. Give your answer modulo $10^9+7$.

随机发牌

用$n$张牌玩一个游戏：游戏开始时，将所有牌发到桌上，组成$n$个单张牌堆。

之后每一轮进行如下行动：

随机选择并拿起一个牌堆；
再从桌上随机选择一个牌堆，将拿起的牌堆最顶上的一张牌放到新选择的牌堆上；
将拿起的牌堆中剩余的牌重新发到桌上，每张牌各自组成一个新的单张牌堆。

当所有牌合并为一个牌堆时，游戏结束。

每一轮行动后，将桌上所有牌堆的大小进行按位异或运算，所得结果即为该轮的得分。游戏结束时，总分为各轮得分之和，并记$X(n)$为总分的期望。

已知$X(2) = 2$，$X(4) = 14$，$X(10) = 1418$。

求$X(10^4)$，并对$10^9+7$取余作为你的答案。