Problem 866

Tidying Up B

A small child has a “number caterpillar” consisting of $N$ jigsaw pieces, each with one number on it, which, when connected together in a line, reveal the numbers $1$ to $N$ in order.

Every night, the child’s father has to pick up the pieces of the caterpillar that have been scattered across the play room. He picks up the pieces at random and places them in the correct order.
As the caterpillar is built up in this way, it forms distinct segments that gradually merge together.

Any time the father places a new piece in its correct position, a segment of length $k$ is formed and he writes down the $k$ th hexagonal number $k \cdot (2 k - 1)$ . Once all pieces have been placed and the full caterpillar constructed he calculates the product of all the numbers written down. Interestingly, the expected value of this product is always an integer. For example if $N = 4$ then the expected value is $994$ .

Find the expected value of the product for a caterpillar of $N = 100$ pieces. Give your answer modulo $987654319$ .

清理（二）

小朋友有一个“数字毛毛虫”玩具，包含有 $N$ 片拼板，分别标有编号；如果把它们都拼起来，将会组成一条直线，且按照 $1$ 到 $N$ 顺序排列。

每天晚上，小朋友的爸爸都要把玩具房里撒了一地的毛毛虫拼板捡起来。他捡的时候是完全随机的，捡起来之后，再按照正确的顺序拼好。
这样一来，毛毛虫拼板将会构成分离的片段，并且不断合并直到组成完整的毛毛虫。

爸爸每将一块拼板拼到正确的位置上，就会形成一个长度为 $k$ 的片段，相应地他会写下第 $k$ 个六边形数 $k \cdot (2 k - 1)$ 。当爸爸完整地拼完毛毛虫后，他会算出写下的所有数的成绩。有趣的是，这一乘积的期望总是整数。例如，若 $N = 4$ ，则期望值为 $994$ 。

若毛毛虫拼板共有 $N = 100$ 片，求此时乘积的期望，并对 $987654319$ 取余作为你的答案。

译注：“清理（一）”参见第253题。