866 : お片付けB

小さな子供が、 $N$ 個のジグソーパズルのピースからなる「数字のキャタピラ」を持っている。 それぞれのピースには数がひとつ書かれており、一列にはめ合わせると、$1$ から $N$ までの数が順に並ぶ。

子供の父親は毎晩、子供部屋のあちこちに散らばったキャタピラの破片を拾う。 彼はピースをランダムに拾い上げ、正しい順序で配置する。 キャタピラがこのように構築されると、分断された区間が徐々に繋がっていく。

父親が新しいピースを正しい位置に置くことで長さ $k$ の区間が形成されるたびに、彼は $k$ 番目の六角数 $k \cdot (2k-1)$ を書き留める。 全てのピースを配置し、キャタピラが完成したら、書き留めた全ての数の積を計算する。 興味深いことに、この積の期待値は常に整数である。 例えば、$N=4$ のとき期待値は $994$ である。

$N=100$ 個のキャタピラの積の期待値を求めよ。$987654319$ を法として答えよ。