---

Problem 823

---

Factor Shuffle

A list initially contains the numbers $2,3,\dots ,n$.

At each round, every number in the list is divided by its smallest prime factor. Then the product of these smallest prime factors is added to the list as a new number. Finally, all numbers that become $1$ are removed from the list.

For example, below are the first three rounds for $n=5$:
$$[2,3,4,5]\stackrel{(1)}{\to }[2,60]\stackrel{(2)}{\to }[30,4]\stackrel{(3)}{\to }[15,2,4].$$
Let $S(n,m)$ be the sum of all numbers in the list after $m$ rounds.

For example, $S(5,3)=15+2+4=21$. Also $S(10,100)=257$.

Find $S({10}^4,{10}^{16})$. Give your answer modulo $1234567891$.

---

因数重排

考虑初始数列$2,3,\dots ,n$。

在每一轮中，将数列中的每个数都除以其最小的质因数，再将这些质因数的乘积加入数列，最后将所有的$1$从数列中移除。

例如，当$n=5$时，前三轮的操作如下：
$$[2,3,4,5]\stackrel{(1)}{\to }[2,60]\stackrel{(2)}{\to }[30,4]\stackrel{(3)}{\to }[15,2,4]$$
记$S(n,m)$为进行$m$轮后数列中所有数之和。

例如，$S(5,3)=15+2+4=21$。已知$S(10,100)=257$。

求$S({10}^4,{10}^{16})$，并将你的答案对$1234567891$取余。

---